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. The program should also tell the path using which the mouse can reach the cheese. It is made clear in the example below:

Example 1:
1100
0111
0010
0090
The mouse can reach 9 in the above array.
Path:
Right
Down
Right
Down
Down

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
 import java.util.Scanner;
 public class MouseAndMaze 
 {
     public static String resultant="";
     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.println();
         if (result==1)
         {
             System.out.println("The mouse can reach the cheese by following the path below: ");
             System.out.println(resultant);
         }
         if (result==0)
             System.out.println("The mouse can not reach the cheese.");
         
     }
     
     public static int maze (int[][] arr,int x,int y)
     {
         if (arr[x][y]==9)
         {
             resultant="Reached the cheese"+"\n"+resultant;
             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 u=0,d=0,r=0,l=0;
         if (y>0)
         {
             u=maze(arr,x,(y-1));
             if (u!=0)
             {
                 resultant="Left"+"\n"+resultant;
                 return 1;
             }
         }
         if (y<yl)
         {
             d=maze(arr,x,(y+1));
             if (d!=0)
             {
                 resultant="Right"+"\n"+resultant;
                 return 1;
             }
         }
         if (x<xl)
         {
             r=maze(arr,x+1,y);
             if (r!=0)
             {
                 resultant="Down"+"\n"+resultant;
                 return 1;
             }
         }
         if (x>0)
         {
             l=maze(arr,x-1,y);
             if (l!=0)
             {
                 resultant="Up"+"\n"+resultant;
                 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 1 1 1 1 1 0 0
0 0 0 0 0 0 1 0 0 1 1 1 0 1 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 1 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 reach the cheese by following the path below: 
Right
Right
Right
Right
Right
Right
Right
Right
Down
Down
Down
Down
Right
Right
Right
Right
Right
Right
Down
Down
Down
Down
Down
Down
Left
Down
Down
Down
Down
Right
Right
Right
Down
Down
Down
Right
Right
Down
Down
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Left
Reached the cheese


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 1 1 1 1 1 0 0
0 0 0 0 0 0 1 0 0 1 1 1 0 1 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 reach the cheese.

Explanation:
Read the Mouse and Maze Part 1 explanation if you have not read it already
  • To achieve the solution for this problem, I am going to make modifications to the code explained in the Part 1.  I have created a static string in the MouseAndMaze class (see line number 4) and it can be modified from any method. The string will be used to store the path to the cheese in the maze.
  • In this program, it will not check each and every path. For example , if there are n paths, it will check the path 1 followed by path 2 and so on. If any path reaches to the cheese, it will skip the other paths. i.e. it return the result rather than checking the other paths too. See the additional if statements at line numbers 51, 60, 69 and 78. Also see the line numbers 54, 63, 72 and 81 for the return statements.
  • It also stores the path in the string declared in line 4. See line numbers 53, 62, 71 and 80.
  • The main method, after getting the result from the maze method displays the output.