Easy understanding BFS Java solution


  • 1
    T
    public class Solution {
        private int[][] dir = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
        private char[] alph = {'d', 'l', 'r', 'u'};
        // dlru {1, 0}, {0, -1}, {0, 1}, {-1, 0}
        
        public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
            if (maze == null || maze.length == 0 || maze[0].length == 0) {
                return "";
            }
            int n = maze.length, m = maze[0].length;
            Queue<int[]> queue = new LinkedList<int[]>();
            queue.offer(ball);
            String[][] path = new String[n][m];
            int[][] step = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    step[i][j] = Integer.MAX_VALUE;
                    path[i][j] = "";   //!!!
                }
            }
            step[ball[0]][ball[1]] = 0;
            
            while (!queue.isEmpty()) {
                int[] point = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int[] d = dir[i];
                    int x = point[0];
                    int y = point[1];
                    if (x == hole[0] && y == hole[1]) {
                        break;
                    }
                    while (x + d[0] >= 0 && x + d[0] < n && y + d[1] >= 0 && y + d[1] < m && maze[x + d[0]][y + d[1]] == 0) {
                        x += d[0];
                        y += d[1];
                        if (x == hole[0] && y == hole[1]) {
                            break;
                        }
                    }
                    int curStep = Math.abs(x - point[0]) + Math.abs(y - point[1]);
                    if (curStep == 0) {
                        continue;
                    }
                    if (step[x][y] > curStep + step[point[0]][point[1]]) {
                        // update step & path, and put point into queue
                        step[x][y] = curStep + step[point[0]][point[1]];
                        path[x][y] = path[point[0]][point[1]] + alph[i];
                        queue.offer(new int[]{x, y});
                    } else if (step[x][y] == curStep + step[point[0]][point[1]]) {
                        // compare path and update path
                        String curPath = path[point[0]][point[1]] + alph[i];
                        path[x][y] = comparePath(curPath, path[x][y]);
                        queue.offer(new int[]{x, y});
                    }
                }
            }
            return step[hole[0]][hole[1]] == Integer.MAX_VALUE? "impossible" : path[hole[0]][hole[1]];
        }
        
        private String comparePath(String s1, String s2) {
            char[] c1 = s1.toCharArray();
            char[] c2 = s2.toCharArray();
            int len = Math.min(c1.length, c2.length);
            for (int i = 0; i < len; i++) {
                if (c1[i] < c2[i]) {
                    return s1;
                }
                if (c1[i] > c2[i]) {
                    return s2;
                }
            }
            return len == c1.length ? s1 : s2;
        }
    }
    

Log in to reply
 

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