/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/**
 * Maze is given as N*N binary matrix of blocks where source block is the upper left most block 
 * i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. 
 * A rat starts from source and has to reach destination. The rat can move only in two directions: forward and down.
 *
 * In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination. 
 * Note that this is a simple version of the typical Maze problem. 
 * For example, a more complex version can be that the rat can move in 4 directions and 
 *	a more complex version can be with limited number of moves.
 */
class Ideone {
	public static void main(String[] args){
		int[][] ratMaze = {
							{1, 0, 0, 0},
							{1, 1, 0, 1},
							{0, 1, 0, 0},
							{1, 1, 1, 1}
						  };
 
		int[][] solution = new int[ratMaze.length][ratMaze[0].length];
		boolean pathExists = isPathExist(ratMaze, solution, 0, 0);
		System.out.println("path exists => "+ pathExists);
 
		//Print path of rat traversal in maze
		for(int i=0; i< solution.length; i++){
			for(int j=0; j< solution[0].length; j++){
				if(solution[i][j] == 1)
				System.out.println("( "+i+ ", "+ j + ")");
			}
		}
	}
 
	private static boolean isPathExist(int[][] maze,int[][] solution, int curX, int curY){
		if(curX < 0 || curX >= maze.length || curY < 0 || curY >= maze.length){
			return false;
		}
 
		if(curX == maze.length-1 && curY == maze[0].length -1){
			solution[curX][curY] = 1;
			return true;
		}
 
		if(maze[curX][curY] == 1){
			solution[curX][curY] = 1;
			//Traversing either right or downward directions
			if(isPathExist(maze, solution, curX +1, curY) || isPathExist(maze, solution, curX, curY + 1)){
				return true;
			}else{
				solution[curX][curY] = 0;	
			}
		}else{
			solution[curX][curY] = 0;
		}
		return false;
	}
}