Problem:
Write a program that will input a 2 D array from the user. The array will be the structure of a maze. The 1s in the array will represent the path where the mouse can move and 0s in the array will represent walls. There is a big piece of cheese in the maze represented by a 9 in the array. The mouse will start moving from the corner (0,0) of the array. The program should tell that the mouse can reach the piece of cheese or not.
Example 1:
1100
0111
0010
0090
The mouse can reach 9 in the above array.
Example 2:
1000
1110
0000
9111
The mouse can’t reach 9 in the above array
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
/** * @author Hafiz Muhammad Umer */ import java.util.Scanner; public class Maze { public static void main(String[] args) { Scanner input=new Scanner(System.in); System.out.print("Enter the number of rows of array: "); int n=input.nextInt(); System.out.print("Enter the number of columns of array: "); int m=input.nextInt(); System.out.println("Enter the array:"); int are[][]=new int[n][m]; for (int t=0;t<n;t++) { for (int T=0;T<m;T++) { are[t][T]=input.nextInt(); } } int result=maze(are,0,0); System.out.print("The mouse can "); if (result==0) System.out.print("not "); System.out.println("get the chese."); } public static int maze (int[][] arr,int x,int y) { if (arr[x][y]==9) { return 1; } if (arr[x][y]==0) { return 0; } int xl=arr.length-1; int yl=arr[1].length-1; arr[x][y]=0; int res=0; int u=0,d=0,r=0,l=0; if (y>0) { u=maze(arr,x,(y-1)); } if (y<yl) { d=maze(arr,x,(y+1)); } if (x<xl) { r=maze(arr,x+1,y); } if (x>0) { l=maze(arr,x-1,y); } res=u+d+r+l; if (res!=0) { return 1; } return 0; } } |
Output:
Enter the number of rows of array: 20 Enter the number of columns of array: 20 Enter the array: 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 The mouse can get the chese.
Enter the number of rows of array: 20 Enter the number of columns of array: 20 Enter the array: 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 The mouse can not get the chese.
Explanation:
- In this program, the problem is solved by recursion. This is the first thing to remember.
- The main method takes the input from the user, passes the required information to the maze method and displays the result on the screen.
- The maze method recurses to find the required output. It will return 1, if the mouse can reach the cheese, otherwise it will return 0.
- Parameters of maze method: It takes three parameters. First is the array that was input from the user. Then there are x and y coordinates of the point from where it has to start looking from. As the program is said to start looking from the point (0,0), the x and y coordinates passed by the main method are both 0. They are changed as the method is recursed.
- The method first checks the “point” (x and y coordinates given as parameter) for the presence of 9 or 0. If 9 is present, it returns 1 i.e. the mouse has reached the cheese and if 0 is present, it returns 0 i.e. the way is blocked. It is clear that this will happen when the array is recursed.
- Then it passes the coordinates of up, down, right and left points to the itself i.e. it recurses. Before doing so, it checks that whether these points exist or not (i.e. It checks if we have reached the boundary of the array). The statements at lines 46, 50, 54 and 58 will make it clear.
- If any of the recursions executed at lines 48, 52, 56 and 60 returns 1 (i.e the mouse has reached the cheese by any path), the method returns 1. It is because, we test many paths in the array. If there is at least one path that can lead the mouse to the cheese, then we can say that the mouse can reach the cheese.
- Note the statement at line number 43. The element of the array which is tested is set to 0. This is done to prevent the control circulation in the loop, if there is any in the maze. For example, consider the maze given in the picture. It is possible that the program keeps on checking the closed path as shown.
