Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 158

findOrg(W...) //returns immediately since G[W] is outside grid
findOrg(W...) //returns immediately since G[W] is outside grid
findOrg(W...) //returns immediately since G[W] is outside grid
When the call findOrg(2, 0, ...) finally returns, G would be changed to this:
0 2 0 3 3 3 0
0 0 3 3 0 0 0
4 4 0 3 0 0 1
4 0 1 0 0 1 1
4 4 0 0 0 1 0
The third organism (labeled 4 ) has been identified. Note that each cell in the organism gave rise to four calls to
findOrg .
5.9 Finding a Path Through a Maze
Consider the following diagram that represents a maze:
##########
# # # #
# # # ## #
# # #
# ###### #
# # #S##
# ## #
##########
Problem: Starting at S and moving along the open spaces, try to find a way out of the maze. The following shows
how to do it with x s marking the path:
##########
# #xxx# #
# #x#x## #
#xxx#xxxx#
#x######x#
#x# #x##xx
#xxxxx## #
##########
We want to write a program that, given a maze, determines whether a path exists. If one exists, mark the path
with x s.
Given any position in the maze, there are four possible directions in which one can move: north (N), east (E),
south (S), and west (W). You will not be able to move in a particular direction if you meet a wall. However, if there is an
open space, you can move into it.
In writing the program, we will try the directions in the order N, E, S, and W. We will use the following strategy:
try N
if there is a wall, try E
else if there is a space, move to it and mark it with x