|
Letīs assume you know a standard way finder algorithm (SWFA) that finds a way from A to B, if there is one. Letīs also assume we have colors "1", "2", "3"... etc. The algorithm is as follows:
On the map, paint every place you can reach with the color "1"; If you painted the exit, then the SWFA will show you the way out, and youīre free!
Assuming you didnīt paint the exit, paint with color "2" every wall that could be breached from a place painted with "1"; if you painted the outside wall, applying the SWFA to reach from the outside wall to a "1" colored place, and again to get from there to the start, will get you out.
Assuming you havenīt excaped yet, paint with color "3" every place you can reach from a place painted with color "2"; if you painted the exit, apply the SWFA to reach from it to a "2" colored place, and again to get to a "1" colored place, and again to get to the starting place, and you are out!
Once again, if you didnīt paint the exit, paint with color "4" every wall that could be breached from a place painted with "3"... and so on; the algorithm is easily generalized.
If you used N colors, then int(N/2) walls had to be breached, and the way out is found by finding a path from color N to color N-1, then from there to color N-2, and so on until you get to the original spot.
|
