麻烦bobo老师帮我看下

来源：7-1 算法笔试面试中的 BFS 问题

慕数据4371709

2021-11-21

力扣1091题也就是您刚刚讲的那题，我尝试用floodfill解法做了一遍，在一个例子上次出了问题，看了很久都想不明白，麻烦波波老师帮我看下

class Solution {
    TreeSet<Integer>[] G;
    int R;
    int [][] dirts = {
            {-1, -1},
            {-1, 0},
            {-1, 1},
            {0, -1},
            {0, 1},
            {1, -1},
            {1, 0},
            {1, 1}
        };

    int[][] grid;
    int length;
    Stack<Integer> stack;
    boolean[] visited;
    int[] pre;
    public int shortestPathBinaryMatrix(int[][] grid) {
        R = grid.length;
        G = new TreeSet[R * R];
        this.grid = grid;
        visited = new boolean[R * R];
        length = 0;
        stack = new Stack<Integer>();
        pre = new int[G.length];

        for(int i = 0; i < R * R; i ++){
            G[i] = new TreeSet<Integer>();
        }

        constructGraph();

        if(!bfs(0)){
            return -1;
        }
        int count = 1;
        int s = R * R - 1;
        while(s != 0){
            s = pre[s];
            count ++;
        }

        return count;

    }

    private boolean inArea(int x, int y){
        return x >= 0 && x < R && y >= 0 && y < R; 
    }
    private void constructGraph(){
        for(int v = 0; v < G.length; v ++){
            int x = v / R;
            int y = v % R;
            if(grid[x][y] != 0){
                continue;
            }
            for(int d = 0; d < 8; d ++){
                int nextx = x + dirts[d][0];
                int nexty = y + dirts[d][1];

                if(inArea(nextx, nexty) && grid[nextx][nexty] == 0){
                    int k = nextx * R + nexty;
                    G[v].add(k);
                    G[k].add(v);
                }
            }

        }
    }

    private boolean bfs(int from){
        pre[from] = from;
        visited[from] = true;
        stack.push(from);
        while(!stack.isEmpty()){
            int x = stack.pop();
            if(x == R * R - 1){
                return true;
            }
            visited[x] = true;
            
            for(int v : G[x]){
                if(!visited[v]){
                    stack.push(v);
                    pre[v] = x;
                }
            }
        }
        return false;
    }
}

出现问题的例子[[0,1,0,0,0,0],[0,1,0,1,1,0],[0,1,1,0,1,0],[0,0,0,0,1,0],[1,1,1,1,1,0],[1,1,1,1,1,0]]

写回答

1回答

liuyubobobo

2021-11-22

已采纳

“也就是您刚刚讲的那题”？我有点儿忘记了。我在哪里讲的这个问题？给我一个链接？

==========

这个问题不是一个 floodfill 的问题，是一个 bfs 的问题。(你的代码中我也没看出 floodfill，但是确实有一个 bfs 的函数。)

你的 bfs 代码有两个问题：

1） bfs 应该使用的是 queue，你使用的是 stack？

2）你的 bfs 过程中对 visited 的赋值有问题。

请再复习一遍 bfs 的基本逻辑。

以下代码是基于你的代码的修改，是正确的。上面说的两个地方我给注释上了。

class Solution {
    TreeSet<Integer>[] G;
    int R;
    int [][] dirts = {
            {-1, -1},
            {-1, 0},
            {-1, 1},
            {0, -1},
            {0, 1},
            {1, -1},
            {1, 0},
            {1, 1}
        };
    int[][] grid;
    int length;
    Queue<Integer> q; // bfs 应该使用 Queue 而非 Stack
    boolean[] visited;
    int[] pre;
    
    public int shortestPathBinaryMatrix(int[][] grid) {
        R = grid.length;
        G = new TreeSet[R * R];
        this.grid = grid;
        visited = new boolean[R * R];
        length = 0;
        q = new LinkedList<Integer>();
        pre = new int[G.length];
        for(int i = 0; i < R * R; i ++){
            G[i] = new TreeSet<Integer>();
        }
        constructGraph();
        
        if(!bfs(0)){
            return -1;
        }
        
        int count = 1;
        int s = R * R - 1;
        while(s != 0){
            s = pre[s];
            count ++;
        }
        return count;
    }
    
    private boolean inArea(int x, int y){
        return x >= 0 && x < R && y >= 0 && y < R; 
    }
    
    private void constructGraph(){
        for(int v = 0; v < G.length; v ++){
            int x = v / R;
            int y = v % R;
            if(grid[x][y] != 0){
                continue;
            }
            for(int d = 0; d < 8; d ++){
                int nextx = x + dirts[d][0];
                int nexty = y + dirts[d][1];
                if(inArea(nextx, nexty) && grid[nextx][nexty] == 0){
                    int k = nextx * R + nexty;
                    G[v].add(k);
                    G[k].add(v);
                }
            }
        }
    }
    
    private boolean bfs(int from){
        pre[from] = from;
        visited[from] = true;
        q.add(from);
        while(!q.isEmpty()){
            int x = q.remove();
            if(x == R * R - 1){
                return true;
            }
            
            for(int v : G[x]){
                if(!visited[v]){
                    q.add(v);
                    pre[v] = x;
                    visited[v] = true; // 入队的节点 visited 就应该赋值为 true
                }
            }
        }
        return false;
    }
}

继续加油！：）

慕数据4371709

谢谢bobo老师

2021-11-22

共1条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1599 学习 · 330 问题

查看课程

相似问题

希望bobo老师可以帮我看一下T T

回答 2