I recently saw someone posted a maze:
Some people say that some small tools on SOHU take it for 20 minutes, and they will be a few minutes. Can you come out for a few minutes? Because I have seen a magazine called "Intelligence" very early (80/90s), there is a complex maze every issue, and the route can form a pattern, so it is also very curious that this maze will come out is a pattern. .
The first flashy thought is the maze algorithm that the Earth people know: the wall is walking, of course, the depth limited / breadth priority search is, the method is very simple, just don't know how long it is .
So I wanted to use something first, I first thought of the brush program, with a filling tool at a white road in the labyrinth, relying on almost half a minute. The result is frustrated, the road to the maze is connected, all the ways are painted. This brush does not know what search algorithm is filled, it is too slow.
It is also called Photoshop, and it is strong, and it is not enough for half a second, it will fill the maze. Unfortunately, the problem is still not resolved. Do you really write a procedure yourself?
Suddenly I thought where I saw a two-dimensional animal problem of "Emperor Xingu"? Is the maze not a two-dimensional animal divided into two halves? "Intestinal" is the route of the maze. So should not be applied to the "road", but should go to the "wall".
Or use the brush, use the filling tool to find a black wall, this is very fast, 1 second, the maze is divided into two halves, the middle boundary is the answer! Very interesting, all such labyrinth should be solved this, do not need any other tools, 1 second can be resolved.
However, it is necessary to say the time complexity of the algorithm. The method of the wall may have a minimum complexity than looking for the road, but the average complexity should be almost.
