fork(16) download
copy 
  1. /**
  2.  * Topic : Backtracking
  3.  *  Rat Maze Problem
  4.  * @author Prateek
  5.  */
  6.  
  7. class SolveMaze {
  8.  
  9. 	int rowLen;  // Lenth 
  10. 	int colLen;
  11. 	int [][] maze;
  12. 	boolean isSolvale;
  13. 	//constructor 
  14. 	public SolveMaze(int maze[][] ){
  15. 		this.rowLen =maze.length -1   ;
  16. 		this.colLen=maze[0].length -1 ;
  17. 		this.maze=maze;
  18. 	}
  19.  
  20. 	/**
  21. 	 * Check Validity of start point
  22. 	 * @return true if points are valid
  23. 	 */
  24. 	private boolean isValidInput(int startRow , int startCol){
  25. 		if(startRow > rowLen || startCol > colLen || startRow < 0 || startCol < 0){
  26. 			return false;}
  27. 		return true;
  28. 	}
  29.  
  30. 	public void solve(int startRow, int startCol){
  31.  
  32.  
  33. 		if(isValidInput(startRow, startCol))
  34. 		{
  35. 			//  solution matrix, initialisation
  36. 			int[][] solution = new int[maze.length][maze[0].length]; 
  37.  
  38. 			solveMaze(maze,solution,startRow, startCol ) ;
  39.  
  40. 			//System.out.println(isSolvale);
  41. 			if(!isSolvale)
  42. 				System.out.println("Path does not exist");
  43. 		}
  44. 		else
  45. 			System.out.println("Invalid Start Point");
  46. 	}
  47.  
  48. 	/**
  49. 	 * Recursive subroutine for the path
  50. 	 * @param maze : input maze
  51. 	 * @param solution : solution of maze
  52. 	 * @param row : current row
  53. 	 * @param col : current col
  54. 	 */
  55. 	private void solveMaze(int maze[][] , int solution[][] , int row, int col) {
  56.  
  57. 		//exit gate reached
  58. 		if(row == rowLen && col == colLen){
  59. 			solution[row][col]=1;
  60. 			printSolution(solution);
  61. 			this.isSolvale=true;
  62. 		}
  63.  
  64. 		// Move Down
  65. 		if(row  < rowLen )
  66. 		{
  67. 			if(maze[row+1][col] == 1) {
  68. 				solution[row][col]=1;
  69. 				solveMaze(maze , solution , row + 1 , col);
  70. 				solution[row][col]=0;
  71. 			}
  72. 		}
  73.  
  74. 		//Move Right
  75. 		if(col  < colLen )
  76. 		{
  77. 			if(maze[row][col+1] == 1) {
  78. 				solution[row][col]=1;
  79. 				solveMaze(maze , solution , row , col +1 );
  80. 				solution[row][col]=0;
  81. 			}
  82. 		}
  83.  
  84. 	}
  85.  
  86.  
  87. 	private void printSolution(int[][] solution) {
  88. 		int rLen=solution.length;
  89. 		int cLen=solution[0].length;
  90.  
  91. 		for(int i=0 ; i  < rLen ;i++ )
  92. 		{
  93. 			for (int j=0 ; j< cLen ;j++)
  94. 			{
  95. 				System.out.print(solution[i][j] + "\t");
  96. 			}
  97. 			System.out.println();
  98. 		}
  99. 	}
  100.  
  101. 	public static void main(String[] args) {
  102. 		int [][] maze =  { {1, 1, 0, 1 , 1 },
  103. 						   {0, 1, 0, 1 , 0 },
  104. 						   {0, 1, 1, 1 , 0 },
  105. 						   {0, 1, 0, 1 , 0 },
  106. 						   {1, 0, 1, 1 , 1 }
  107. 						};
  108.  
  109. 		SolveMaze obj=new SolveMaze(maze) ;
  110. 		obj.solve(0, 0);
  111. 	}
  112. }
  113.  
Success #stdin #stdout 0.06s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1	1	0	0	0	
0	1	0	0	0	
0	1	1	1	0	
0	0	0	1	0	
0	0	0	1	1
https://ideone.com/pYxNey
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!