XXXX
X*$X
XXXX
The optimal path is 1 steps.
XXXXXXXXX
X X...X X
X X.X.X X
X X.X.X X
X X.X.X X
X X.X.X X
X X.X.X X
X*..X..$X
XXXXXXXXX
The optimal path is 18 steps.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X             X             X
X XXXXXXXXXXX X XXXXXXXXXXX X
X X           X           X X
X X XXXXXXXXXXXXXXXXXXXXX X X
X X           X           X X
X XXXXXXXXXXX X XXXXXXXXXXX X
X X           X           X X
X X           X           X X
X X           X           X X
X X           X           X X
X X           X           X X
X X           X           X X
X X           X           X X
X X           X           X X
X X           X           X X
X X           X           X X
X X           X           X X
X X                       X X
X XXXXXXXXXXXXXXXXXXXXXXXXX X
X...........................X
X.XXXXXXXXXXXXXXXXXXXXXXXXX.X
X.X           X...........X.X
X.X           X.XXXXXXXXX.X.X
X.X           X.X.........X.X
X.X           X.X.XXXXXXXXX.X
X.X           X.X.........X.X
X.X           X.XXXXXXXXX.X.X
X.X           X.X        .X.X
X.X           X.X        .X.X
X.X           X.X        .X.X
X.X           X.X        .X.X
X.X           X.X        .X.X
X.X           X.X        .X.X
X.X           X.X        .X.X
X.X           X.X        .X.X
X.X           X.X        .X.X
X.X*..........X.X        $X.X
X.XXXXXXXXXXX.X.XXXXXXXXXXX.X
X.............X.............X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
The optimal path is 158 steps.
XXXXXXXXXXXXXXX
X             X
X XXXXXXXXXXX X
X X         X X
X X XXXXXXX X X
X X X  $  X X X
X X XXXXXXX X X
X X         X X
X X XXXXXXXXX X
X            *X
XXXXXXXXXXXXXXX
This maze has no solutions.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X                   *X$                 X
X                    X                  X
X                    X                  X
X                    X                  X
X                    X                  X
X                    X                  X
X                    X                  X
X                    X                  X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
This maze has no solutions.
XXXXXXXXXXXXXXXXXXX
X$................X
XXXXXXXXXXXXXXXXX.X
X...X           X.X
X.X.XXXXXXXXXXX X.X
X.X.X...........X.X
X.X.X.XXXXXXXXX.X.X
X.X.X.X*......X.X.X
X.X.X.XXXXXXX.X.X.X
X.X.X.........X.X.X
X.X.XXXXXXXXXXX.X.X
X.X.............X.X
X.XXXXXXXXXXXXXXX.X
X.................X
XXXXXXXXXXXXXXXXXXX
The optimal path is 112 steps.