BOI 2013 - Tracks in the Snow
Problem Link Tags: BOI, graph, 01 BFS, shortest paths Time Complexity: O(HW) This problem uses 0-1 BFS. This is from where I learnt 0-1 BFS. In this problem, a grid is given which consists of . (empty square), R (rabbit) and F (foxes). Given the the grid and its dimensions, we are asked to find out the minimum number of animals that could have been present on the grid in total. (Tricky Test Case - the answer is 3 - minimum of two foxes and one rabbit) Original Fox 1 Rabbit 1 Fox 2 - (back to original) This problem is a graph problem, because every square can be considered as a node, and an edge can be drawn between any two adjacent nodes. There are 3 options for every pair of adjacent nodes: If either of the 2 nodes were not visited by any animal, then that node(s) should not be included in the node. So, no edge should be drawn here. If the 2 nodes were last visited by the same animal, ...