二分+BFS解决leetcode 505的问题

Question

bobo老师，除了用Dijkstra之外，我尝试用二分搜索+BFS解决leetcode 505 The Maze II，但是只有70/78个case能通过，不知为何。能否请您拨冗看下代码，思路出在哪里？

我的思路是。因为maze矩阵的长、宽的范围是[0,100]，所以二分的上下界是[0, 10001]。二分的目的是，找到start到destination的最短距离，如果不能到达，返回-1。 每次二分搜索确定一个值len，相当于给bfs添加了一个剪枝策略，当走过的distance大于len时，停止当前搜索。如果在len的限制下找到了从start到destination的路径，则利用二分继续向下寻找更小的distance。

但是在一个错误用例上，我的输出是204，正确答案是192。因为数据范围很大，我不太确定问题出在哪，所以想请您看下思路和代码哪里出现了问题，谢谢老师！

class Solution {
    
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        
       
        int l = 1, r = 10001;
        
        while (l < r) {
            int mid = l + (r - l) / 2;
            
            if (hasPath(mid, maze, start, destination))
                r = mid;
            else
                l = mid + 1;
        }
        
        return l == 10001 ? -1 : l;
    
    }
    
    private boolean hasPath(int len, int[][] maze, int[] start, int[] destination) {
        
        int m = maze.length;
        int n = maze[0].length;
        
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> q = new ArrayDeque<>();
        
        q.offer(new int[]{start[0] * n + start[1], 0});
        visited[start[0]][start[1]] = true;
        
        while (!q.isEmpty()) {
            int x = q.peek()[0] / n;
            int y = q.peek()[0] % n;
            int distance = q.peek()[1];
            q.poll();
            
            if (distance + 1 > len)
                continue;
            
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                int steps = 1;
                
                if (!inArea(nx, ny, maze) || visited[nx][ny] || maze[nx][ny] == 1)
                    continue;
                
                while (inArea(nx, ny, maze) && maze[nx][ny] == 0) {
                    nx += dx[k];
                    ny += dy[k];
                    steps++;
                }
                
                // 恢复最后一个合法状态
                nx -= dx[k];
                ny -= dy[k];
                steps--;
                
                // 剪枝
                if (distance + steps > len)
                    continue;
                
                if (nx == destination[0] && ny == destination[1])
                    return true;
                
                if (!visited[nx][ny]) {
                    q.offer(new int[]{nx*n + ny, distance + steps});
                    visited[nx][ny] = true;
                }
                
            }
        }
        
        return false;
    }
    
    private boolean inArea(int x, int y, int[][] maze) {
        return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length;
    }
}

Answer 1

liuyubobobo 2022-07-05 00:45:27

因为二分 + BFS 求解带权图的最短路径的思路就是错的，因为 BFS 的过程没有松弛。（我记得我之前回答过你这个问题。但是你之前提的另一个问题，因为在路径上的操作是 max 和 min，而不是加法，所以没有这个问题。）

请你脱离开这个问题的背景，写一个基于你的二分 + BFS 的算法，求解最短路径问题，输入是像课程中定义的图的方式，把代码给我，我看一下是不是比较容易给你设计一个反例。

继续加油！：)

• 提问者 讲武德的年轻人 #1

  多谢bobo老师。我知道问题在哪了。在BFS中，我用的框架跟LC 490 Maze I类似，用visited标记访问过的结点。但是先访问的结点不一定是最短的结点，所以我按照您课程的思路，用一个int[][]距离矩阵来维护是否入队，即只有距离更短时才入队更新。这样就可以通过了，但是速度上比Dijkstra要差。谢谢老师指点！