fork(8) download
copy 
  1. /**
  2.  * Find the way through the maze, also find the key
  3.  * @author Prateek
  4.  */
  5. class MazeWithKey {
  6. 	static int N;
  7. 	static int size;
  8. 	static boolean isKeyFound=false;
  9. 	static int[][] solution;
  10.  
  11. 	private static boolean solveMaze(int maze[][] , int solution[][] , int row , int col){
  12.  
  13. 		// exit gate reached
  14. 		if (row == size && col == size) {
  15. 			if(isKeyFound){
  16. 				solution[row][col] = 1;
  17. 				System.out.println("Path Marix is :");
  18. 				printSolution(solution);
  19. 				System.out.println("===============================");
  20. 				return true;
  21. 			}
  22. 		}
  23.  
  24. 		// Move Down
  25. 		if (row < size)
  26. 		{
  27. 			if (maze[row + 1][col] == 1 || maze[row + 1][col] == 2) 
  28. 			{
  29. 				if(solution[row + 1][col] != 1){ //to avoid re-selecting the same cell
  30.  
  31. 					if(maze[row + 1][col] == 2){
  32. 						isKeyFound=true;
  33. 					}
  34.  
  35. 					solution[row][col] = 1;
  36. 					solveMaze(maze, solution, row + 1, col);
  37. 					solution[row][col] = 0;
  38.  
  39. 					if(maze[row + 1][col] == 2){
  40. 						isKeyFound=false;
  41. 					}
  42. 				}
  43. 			}
  44. 		}
  45.  
  46. 		// Move Right
  47. 		if (col < size)
  48. 		{
  49. 			if (maze[row][col + 1] == 1 || maze[row][col + 1] == 2)
  50. 			{
  51. 				if(solution[row][col + 1] != 1){
  52.  
  53. 					if(maze[row][col + 1] == 2){
  54. 						isKeyFound=true;
  55. 					}
  56.  
  57. 					solution[row][col] = 1;
  58. 					solveMaze(maze, solution, row, col + 1);
  59. 					solution[row][col] = 0;
  60.  
  61. 					if(maze[row][col + 1] == 2){
  62. 						isKeyFound=false;
  63. 					}
  64. 				}
  65. 			}
  66. 		}
  67.  
  68. 		// Move Up
  69. 		if (row > 0)
  70. 		{
  71. 			if (maze[row - 1][col] == 1 || maze[row - 1][col] == 2) 
  72. 			{
  73. 				if(solution[row - 1][col] != 1){
  74.  
  75. 					if(maze[row - 1][col] == 2){
  76. 						isKeyFound=true;
  77. 					}
  78.  
  79. 					solution[row][col] = 1;
  80. 					solveMaze(maze, solution, row - 1, col);
  81. 					solution[row][col] = 0;
  82.  
  83. 					if(maze[row - 1][col] == 2){
  84. 						isKeyFound=false;
  85. 					}
  86. 				}
  87. 			}
  88. 		}
  89.  
  90. 		// Move Left
  91. 		if (col > 0)
  92. 		{
  93. 			if (maze[row][col -1] == 1 || maze[row][col -1] == 2)
  94. 			{
  95.  
  96. 				if(solution[row][col -1] != 1){
  97.  
  98.  
  99. 					if(maze[row][col -1] == 2){
  100. 						isKeyFound=true;
  101. 					}
  102.  
  103. 					solution[row][col] = 1;
  104. 					solveMaze(maze, solution, row, col -1);
  105. 					solution[row][col] = 0;
  106.  
  107. 					if(maze[row][col -1] == 2){
  108. 						isKeyFound=false;
  109. 					}
  110. 				}
  111. 			}
  112. 		}
  113.  
  114. 		//Move NW
  115. 		if (row > 0 && col > 0 )
  116. 		{
  117. 			if (maze[row - 1][col - 1] == 1 || maze[row - 1][col - 1] == 2) 
  118. 			{
  119. 				if(solution[row - 1][col - 1] != 1){
  120.  
  121. 					if(maze[row - 1][col - 1] == 2){
  122. 						isKeyFound=true;
  123. 					}
  124.  
  125. 					solution[row][col] = 1;
  126. 					solveMaze(maze, solution, row - 1, col - 1);
  127. 					solution[row][col] = 0;
  128.  
  129. 					if(maze[row - 1][col - 1] == 2){
  130. 						isKeyFound=false;
  131. 					}
  132. 				}
  133. 			}
  134. 		}
  135.  
  136. 		//Move NE
  137. 		if (row > 0 && col < size )
  138. 		{
  139. 			if (maze[row - 1][col + 1] == 1 || maze[row - 1][col + 1] == 2) 
  140. 			{
  141. 				if(solution[row - 1][col + 1] != 1){
  142.  
  143. 					if(maze[row - 1][col + 1] == 2){
  144. 						isKeyFound=true;
  145. 					}
  146.  
  147. 					solution[row][col] = 1;
  148. 					solveMaze(maze, solution, row - 1, col + 1);
  149. 					solution[row][col] = 0;
  150.  
  151. 					if(maze[row - 1][col + 1] == 2){
  152. 						isKeyFound=false;
  153. 					}
  154. 				}
  155. 			}
  156. 		}
  157.  
  158.  
  159. 		//Move SE
  160. 		if (row < size && col < size )
  161. 		{
  162. 			if (maze[row + 1][col + 1] == 1 || maze[row + 1][col + 1] == 2) 
  163. 			{
  164. 				if(solution[row + 1][col + 1] != 1){
  165. 					if(maze[row + 1][col + 1] == 2){
  166. 						isKeyFound=true;
  167. 					}
  168.  
  169. 					solution[row][col] = 1;
  170. 					solveMaze(maze, solution, row + 1, col + 1);
  171. 					solution[row][col] = 0;
  172.  
  173. 					if(maze[row + 1][col + 1] == 2){
  174. 						isKeyFound=false;
  175. 					}
  176. 				}
  177. 			}
  178. 		}
  179.  
  180. 		//Move SW
  181. 		if (row < size && col > 0 )
  182. 		{
  183. 			if (maze[row + 1][col - 1] == 1 || maze[row + 1][col - 1] == 2) 
  184. 			{
  185. 				if(solution[row + 1][col - 1] != 1){
  186. 					if( maze[row + 1][col - 1] == 2){
  187. 						isKeyFound=true;
  188. 					}
  189.  
  190. 					solution[row][col] = 1;
  191. 					solveMaze(maze, solution, row + 1, col - 1);
  192. 					solution[row][col] = 0;
  193.  
  194. 					if( maze[row + 1][col - 1] == 2){
  195. 						isKeyFound=false;
  196. 					}
  197. 				}
  198. 			}
  199. 		}
  200.  
  201. 		return false;
  202. 	}
  203.  
  204. 	private static void printSolution(int[][] solution) {
  205. 		int rLen = solution.length;
  206. 		int cLen = solution[0].length;
  207.  
  208. 		for (int i = 0; i < rLen; i++)
  209. 		{
  210. 			for (int j = 0; j < cLen; j++)
  211. 			{
  212. 				System.out.print(solution[i][j] + "\t");
  213. 			}
  214. 			System.out.println();
  215. 		}
  216. 	}
  217.  
  218. 	public static void main(String[] args) {
  219. 		MazeWithKey mazeObj=new MazeWithKey();
  220. 		mazeObj.init();
  221. 	}
  222.  
  223.  
  224. 	private void init(){
  225. 		int[][] maze = { 
  226. 				{1, 1, 0, 0, 1, 1 }, 
  227. 				{1, 0, 1, 1, 0, 0 },
  228. 				{1, 0, 0, 0, 1, 0 }, 
  229. 				{1, 1, 1, 2, 0, 0 },
  230. 				{1, 0, 0, 0, 0, 0 },
  231. 				{1, 1, 1, 1, 1, 1 }
  232. 		};
  233.  
  234.  
  235. 		size = maze.length - 1;
  236.  
  237. 		int[][] solution= new int[maze.length][maze[0].length];
  238.  
  239. 		System.out.println("Input Matrix is ");
  240. 		printSolution(maze);
  241.  
  242. 		System.out.println("===========================");
  243. 		solveMaze(maze,solution, 0 ,0 );
  244. 	}
  245. }
  246.  
Success #stdin #stdout 0.06s 381248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input Matrix is 
1	1	0	0	1	1	
1	0	1	1	0	0	
1	0	0	0	1	0	
1	1	1	2	0	0	
1	0	0	0	0	0	
1	1	1	1	1	1	
===========================
Path Marix is :
1	1	0	0	0	0	
1	0	1	1	0	0	
0	0	0	0	1	0	
1	1	1	1	0	0	
1	0	0	0	0	0	
1	1	1	1	1	1	
===============================
https://ideone.com/aPWGlp
language:
Java (12.0.1)
created:
11 years ago
visibility:
secret

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!