I can’t understand the greedy algorithm they apply in paragraph 4.
“Now consider the following greedy
algorithm: at any step we simply visit all reachable cells, as long as there are unvisited cells (this
algorithm processes the animals in reverse order). Note that the animal we choose at each step is
given by the remarks above.”
Exactly what do they mean here by visiting all reachable cells, as long as there are unvisited cells?
Do they mean that we will try to reach all the cells possible for the animal that is not last. Like rabbit if the topmost footprint was by a fox. And then erase all the rabbit marks and try to reach the end like using fox marks and then erase them and so on?
Can someone elaborate, what exactly the algorithm here is.
Thanks.
In the context of the given description, the algorithm suggests a greedy approach where you visit all reachable cells until there are no unvisited cells left. Here’s a step-by-step explanation of the algorithm:
Start by identifying the animal that made the topmost footprint. Let’s assume it’s a fox.
Visit all the cells that can be reached by a fox from the current position. This means moving horizontally or vertically (not diagonally) to adjacent cells. Mark each visited cell as visited by a fox.
Once all reachable cells for the fox are visited, erase the fox marks from those cells.
Repeat steps 1-3 for the next animal in the reverse order. Let’s say the next animal is a rabbit.
Visit all the cells that can be reached by a rabbit from the current position. Mark each visited cell as visited by a rabbit.
Erase the rabbit marks from the visited cells.
Repeat steps 4-6 for the remaining animals in reverse order.
Continue this process until all animals have been visited and their marks erased.
The algorithm essentially visits all reachable cells for each animal, erasing their marks before moving on to the next animal. By processing the animals in reverse order, it ensures that each animal’s marks are cleared before the next animal is considered. This approach allows you to explore all possible paths for each animal while ensuring that no animal’s marks interfere with another animal’s path.