MazeMan
Jump to navigation
Jump to search
This problem gives us and ASCII maze with a few entrances and tells us how many dots are reachable, and how many different entrances we have to use to reach these dots.
In short, it's asking us how many connected components there are.
This is a relatively straightforward flood-fill problem, whereby we walk around the permiter of the maze to find an un-used entrance, and flood fill. If we ecounter any dots on this fill, we increment our count by 1. We also mark any exits we find on this fill visited. We continue until we have filled from all unvisited entrances, and have thus counted the number needed to visit as many dots as possible. We can iterate through the maze to identify any unreached dots.