public class RatMaze {
public static void main(String[] args) {
int [][] way = {{1,1,0,1},
{0,1,1,1},
{1,1,0,1},
{0,1,1,1}};
findWay(way);
}
private static void findWay(int[][] way) {
int[][] visited = new int[way.length][way[0].length];
//printWay(visited);
int[] xPath = {0 , 0, 1, -1};
int[] yPath = {1, -1, 0, 0};
int destRow = way.length-1;
int destCol = way[0].length-1;
visited[0][0] = 1;
if(!solveWayUtil(0,0,way,visited, xPath, yPath, destRow, destCol, 1)){
System.out.println("no path !!! :( invalid ");
return;
}
return;
}
private static boolean solveWayUtil(int row, int col, int[][] way, int[][] visited, int[] xPath, int[] yPath, int destRow, int destCol, int loc) {
if(row == destRow && col == destCol){
//System.out.println("co "+destRow +" "+destCol +" "+row+" "+col +" "+ (co++));
printWay(visited);
return true;
}
boolean result = false;
for(int i=0;i<xPath.length;i++){
int xPathNew = row + xPath[i];
int yPathNew = col + yPath[i];
if(isValid(xPathNew, yPathNew, way, visited)){
loc++;
visited[xPathNew][yPathNew] = loc;
result = solveWayUtil(xPathNew, yPathNew, way, visited, xPath, yPath, destRow, destCol, loc) || result;
loc--;
visited[xPathNew][yPathNew] = 0;
}
}
return result;
}
private static boolean isValid(int row, int col, int[][] way, int[][] visitd) {
return row>=0 && row<4 && col>=0 && col<4 && way[row][col] == 1 && visitd[row][col] == 0;
}
static void printWay(int[][] way){
for(int i=0;i<way.length;i++){
for(int j=0;j<way[0].length;j++){
System.out.print(way[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
}