Solving Java Mazes

[anon538]

Hello. I'd like to start off by saying that this is not a homework problem of any sort. I am a high school student who frequents cs competitions, and I have never been able to solve problems concerning mazes. For instance, consider the following typical example:

s1000
01000
01000
01111
00101
e1111

The s and e represent starting positions, while the 0's represent "walls" or areas that cannot be traversed. The 1's signify traversable spaces. The object is to find the shortest length from start to end, in this case 9 moves.

I have googled around for solutions to this kind of problem, and have found ones that are either too robust (I want only a few methods inside a single class) or too complex (I must be able to memorize the code to some degree).

I am sure that a concise solution exists, and I would appreciate any help.

Thanks in advance,
anon

[Nepomuk]

Hi anon538!
I think what you should be trying to do is to implement a Breadth-first search. (Example implementations in Python, C and C++ can be found on wikipedia.) In the maze you gave, any search would go the same with most searches until this point:

sv000
0v000
0v000
0vv11
00101
e1111

(v being a visited point)
Then a Breadth-first search would explore the two neighbouring 1s, then those next to them and so on. The first solution that you find that way will be an ideal (= shortest) solution.

Greetings,
Nepomuk