| 1 | class Solution { |
| 2 | public static void backTrack(int r, int c, int m[][], int n, ArrayList<String> list, String path, int visited[][]) |
| 3 | { |
| 4 | // Dead Ends |
| 5 | if(r<0 || c<0 || r>=n || c>=n || visited[r][c]==1 || m[r][c]==0) |
| 6 | { |
| 7 | if(path.length()>1) |
| 8 | path=path.substring(0,path.length()-1); |
| 9 | else |
| 10 | path=""; |
| 11 | return; |
| 12 | } |
| 13 | // Base Case |
| 14 | if(r==n-1 && c==n-1) |
| 15 | { |
| 16 | list.add(path); |
| 17 | return; |
| 18 | } |
| 19 | visited[r][c]=1; |
| 20 | backTrack(r+1,c,m,n,list,path+"D",visited); |
| 21 | backTrack(r,c-1,m,n,list,path+"L",visited); |
| 22 | backTrack(r,c+1,m,n,list,path+"R",visited); |
| 23 | backTrack(r-1,c,m,n,list,path+"U",visited); |
| 24 | // backtrack |
| 25 | visited[r][c]=0; |
| 26 | } |
| 27 | public static ArrayList<String> findPath(int[][] m, int n) { |
| 28 | // Your code here |
| 29 | ArrayList<String> list = new ArrayList<String>(); |