Easy BFS(21ms)/ DFS(45ms)in Java


  • 0
    L

    This is the BFS solution:

    public class Solution {
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            int m = maze.length, n = maze[0].length;
            int[][] length = new int[m][n];
            
            String[][] path = new String[m][n];
            for(String[] items : path)
                Arrays.fill(items, new String());
            
            Queue<int[]> q = new LinkedList<>();
            
            int[] dx = {1, 0, 0, -1};
            int[] dy = {0, -1, 1, 0};
            char[] step = {'d', 'l', 'r', 'u'};
            
            q.offer(ball);
            
            while(!q.isEmpty()) {
                int[] cur = q.poll();
                
                if(Arrays.equals(cur, hole)) continue;
                
                for(int k = 0; k < 4; k++) {
    
                    int i = cur[0], j = cur[1];
                    int count = 0;
                    while((i != hole[0] || j != hole[1]) && i + dx[k] >= 0 && i + dx[k] < m &&
                            j + dy[k] >= 0 && j + dy[k] < n &&
                                maze[i + dx[k]][j + dy[k]] == 0) {
                        count++; i += dx[k]; j += dy[k];
                    }
                    
                    if((i != ball[0] || j != ball[1]) &&
                        (length[i][j] == 0 || length[i][j] > length[cur[0]][cur[1]] + count || 
                            (length[i][j] == length[cur[0]][cur[1]] + count && 
                             path[i][j].compareTo(path[cur[0]][cur[1]] + step[k]) > 0))) {
                        
                        path[i][j] = path[cur[0]][cur[1]] + step[k];
                        length[i][j] = length[cur[0]][cur[1]] + count;
    
                        q.offer(new int[] {i, j});
                    }
                }
            }
            
            return path[hole[0]][hole[1]].length() == 0 ? "impossible" : path[hole[0]][hole[1]];
        }
    }
    

    DFS solution which is similar to backtrace solution:

    public class Solution {
        public String res = new String();
        public int[][] delta = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
        public char[] step = {'d', 'l', 'r', 'u'};
        
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            int[][] path = new int[maze.length][maze[0].length];
            helper(maze, path, ball, new StringBuffer(), hole, ball);
            return res.length() == 0 ? "impossible" : res;
        }
        
        public void helper(int[][] maze, int[][] path, int[] s, StringBuffer sb, int[] hole, int[] ball) {
            if(Arrays.equals(s, hole)) {
                res = sb.toString();
                return;
            }
            
            for(int k = 0; k < 4; k++) {
                int i = s[0], j = s[1],  count = 0;
                
                while((i != hole[0] || j != hole[1]) &&
                        i + delta[k][0] >= 0 && i + delta[k][0] < maze.length &&
                            j + delta[k][1] >= 0 && j + delta[k][1] < maze[0].length &&
                                maze[i + delta[k][0]][j + delta[k][1]] == 0) {
                    i += delta[k][0]; j += delta[k][1]; count++;
                }
                
                if((i != ball[0] || j != ball[1]) && 
                        (path[i][j] == 0 || path[i][j] > path[s[0]][s[1]] + count)) {
                    path[i][j] = path[s[0]][s[1]] + count;
                    sb.append(step[k]);
                    helper(maze, path, new int[] {i, j}, sb, hole, ball);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
      
    }
    

Log in to reply
 

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