package general;

/**
 * You are given a maze (2D boolean matrix) where 0 = free way, 1= obstacle.
 * Write a function to find out many ways exist to reach [N][M] from [0][0].
 */
public class Maze {
	public static long findNumWays(boolean[][] maze) {
		if (maze == null) {
			return 0;
		}

		boolean[][] visited = new boolean[maze.length][maze[0].length];
		return findNumWays(maze, 0, 0, visited);
	}

	private static long findNumWays(boolean[][] maze, int row, int col,
			boolean[][] visited) {
		if (!isValid(maze, row, col) || visited[row][col] || !maze[row][col]) {
			return 0L;
		}

		if (endOfMaze(maze, row, col)) {
			return 1L;
		}

		visited[row][col] = true;

		long numWays = 0L;
		numWays += findNumWays(maze, row - 1, col, visited);
		numWays += findNumWays(maze, row + 1, col, visited);
		numWays += findNumWays(maze, row, col + 1, visited);
		numWays += findNumWays(maze, row, col - 1, visited);

		visited[row][col] = false;
		return numWays;
	}

	private static boolean endOfMaze(boolean[][] maze, int row, int col) {
		return maze != null && row == maze.length - 1
				&& col == maze[0].length - 1;
	}

	private static boolean isValid(boolean[][] maze, int row, int col) {
		return maze != null && row >= 0 && row < maze.length && col >= 0
				&& col < maze[0].length;
	}
}

@@ -65,17 +65,20 @@
 ) where 
-0
+true
  = free 
@@ -86,10 +86,18 @@
 ay, 
-1=
+false =%0A *
  obs
@@ -102,19 +102,16 @@
 bstacle.
-%0A *
  Write a
@@ -132,16 +132,20 @@
 ind out 
+how 
 many way
@@ -167,16 +167,19 @@
 h %5BN%5D%5BM%5D
+%0A *
  from %5B0

Fix comment