在二维矩阵中一次走 2 步

Question

给你一个 MxN 二维网格，用这三个可能的值初始化。

-1 - 一堵墙或障碍物。

0 - 门。

INF - 无限意味着一个空房间

用到最近大门的距离填充每个空房间。

例如，给定二维网格：

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
0    -1 INF INF

运行函数后，二维网格应该是：

3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4

我用的是BFS，从每个0（门）开始，不断更新每个INF的最小值。下面是我的代码，它有效。

public void wallsAndGates(int[][] rooms) {
    if(rooms==null || rooms.length==0) return;
    int row=rooms.length;
    int col=rooms[0].length;
    Queue<Integer> q=new LinkedList<Integer>();
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(rooms[i][j]==0) {
                boolean[][] visited=new boolean[row][col];
                q.add(i*col+j);
                bfs(rooms,q,visited);
            }
        }
    }
}  

public void bfs(int[][] rooms, Queue<Integer> q, boolean[][] visited){
    int row=rooms.length;
    int col=rooms[0].length;
    int distance=1;
    while(!q.isEmpty()){
        int size=q.size();
        for(int m=0; m<size; m++){
            int num=q.poll();
            int i=num/col;
            int j=num%col;
            if(j-1>=0 && rooms[i][j-1]!=0 && rooms[i][j-1]!=-1 && !visited[i][j-1]){
                rooms[i][j-1]=Math.min(rooms[i][j-1],distance);
                q.add(i*col+j-1);
                visited[i][j-1]=true;
            }
            if(j+1<rooms[0].length && rooms[i][j+1]!=0 && rooms[i][j+1]!=-1 && !visited[i][j+1]){
                rooms[i][j+1]=Math.min(rooms[i][j+1],distance);
                q.add(i*col+j+1);
                visited[i][j+1]=true;
            }
            if(i-1>=0 && rooms[i-1][j]!=0 && rooms[i-1][j]!=-1 && !visited[i-1][j]){
                rooms[i-1][j]=Math.min(rooms[i-1][j],distance);
                q.add((i-1)*col+j);
                visited[i-1][j]=true;
            }
            if(i+1<rooms.length && rooms[i+1][j]!=0 && rooms[i+1][j]!=-1 && !visited[i+1][j]){
                rooms[i+1][j]=Math.min(rooms[i+1][j],distance);
                q.add((i+1)*col+j);
                visited[i+1][j]=true;
            }
       }
       distance++;
    }
}

但是，如果我们可以一次执行 2 个步骤，如 "left left" 或 "right up"，会怎样呢？那么如何计算每个INF到它最近的门（0）的距离呢？我们还能使用 BFS 吗？

Answer 1

当然可以。现在您正在测试坐标：

(i+1, j)
(i,   j+1)
(i-1, j)
(i,   j-1)

对应于紧靠 (i, j) 的北、南、东、西的值。只需添加以下测试：

(i+1, j+1)
(i-1, j-1)
(i+1, j-1)
(i-1, j+1)

对应于(i, j)周围的对角线。

编辑：原文看错了post。您还需要添加任何其他可能的组合，例如 (i+2, j)，它对应于 "right right"。在开始之前绘制可能结果的图表并列出完整列表将很有帮助。

小心一点。您的代码很乱，添加这四个语句时很容易出错。慢慢来，仔细检查你的工作。

在二维矩阵中一次走 2 步

Take 2 steps at a time in a 2d matrix

java

matrix

breadth-first-search