Java DFS memoization 13ms 60lines


  • 0
    A
    public class Solution {
        int[][] minDis;
        String[][] path;
        int m, n;
        final int[][] dirs = new int[][] {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
        final char[] cd = new char[] {'d', 'l', 'r', 'u'}; 
        
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            m = maze.length;
            if (m == 0)
                return "";
            n = maze[0].length;
            minDis = new int[m][n];
            path = new String[m][n];
            
            maze[hole[0]][hole[1]] = 2;
            minDis[hole[0]][hole[1]] = 0;
            path[hole[0]][hole[1]] = "";
            
            int res = helper(ball[0], ball[1], maze); 
            if (res == -1)
                return "impossible";
            else
                return path[ball[0]][ball[1]];
        }
        
        public int helper(int i, int j, int[][] maze) {
            if (path[i][j] != null)
                 return minDis[i][j];
            maze[i][j] = -1;
            int min = Integer.MAX_VALUE;
            String str = "";
            for (int k = 0; k < 4; k++) {
                int[] dir = dirs[k];
                int ni = i, nj = j;
                int dis = 0;
                do {
                    ni += dir[0];
                    nj += dir[1];
                    dis++;
                } while (ni >= 0 && nj >=0 && ni < m && nj < n && maze[ni][nj] == 0);
                if (ni < 0 || nj < 0 || ni >=m || nj >= n || maze[ni][nj] == 1) {
                    ni -= dir[0];
                    nj -= dir[1];
                    dis--;
                }
                if (maze[ni][nj] != -1) {
                    int disToHole = helper(ni, nj, maze);
                    if (disToHole != -1 && dis + disToHole < min) {
                        min = dis + disToHole;
                        str = cd[k] + path[ni][nj];
                    }
                }
            }
            maze[i][j] = 0;
            if (min == Integer.MAX_VALUE)
                min = -1;
            else {
                minDis[i][j] = min;
                path[i][j] = str;
            }
            return min;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.