具有1的最近单元格的距离

Question

给定一个大小为N×m的二进制矩阵，任务是为每个单元寻找矩阵中最近的1的距离。该距离计算为I1-I2+J1-J2，其中i1、j1是当前单元的行号和列号，i2、j2是最近单元的行号和列号，其值为1。

输入：输入的第一行是表示测试用例数量的整数T。然后T测试用例就会接踵而至。每个测试用例由2行组成。每个测试用例的第一行包含两个表示矩阵行数和列数的整数M和N。然后在下一行中是矩阵（mat）的n*m个空格分隔的值。

下面是我的代码：

class GFG {
public static void markNearest(int R, int C, int[][] M,int[][] out,Queue<Vertex> q, boolean[][] visited){
    int[] x_pos ={1,-1,0,0};
    int[] y_pos ={0,0,-1,1};
    while(!q.isEmpty()){
        Vertex v = q.poll();
        int x = v.i;
        int y = v.j;
        int d = v.dist;
        
        visited[x][y] = true;
        for(int k=0;k<=3;k++){
            if(isSafe(x+x_pos[k],y+y_pos[k],R,C,visited)){
                if(out[x+x_pos[k]][y+y_pos[k]] == -1){
                    out[x+x_pos[k]][y+y_pos[k]] = d+1;
                    q.add(new Vertex(x+x_pos[k],y+y_pos[k],d+1));
                }
            }
        }
    }
    
    
}

private static boolean isSafe(int i, int j, int r, int c, boolean[][] visited) {
    return (i >= 0 && i < r && j >= 0 && j < c && !visited[i][j]);
}

private static void printMatrixInline(int[][] M) {
    for(int i=0;i<M.length;i++) {
        for(int j=0;j<M[0].length;j++) {
            System.out.print(M[i][j]+" ");
        }
    }
}
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for (int t = 0; t < T; t++) {
        int R = sc.nextInt();
        int C = sc.nextInt();
        int[][] M = new int[R][C];
        int[][] out = new int[R][C];
        Queue<Vertex> q = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                M[i][j] = sc.nextInt();
                if(M[i][j] ==1){
                    q.add(new Vertex(i,j,0));
                    out[i][j] = 0;
                }
                else{
                    out[i][j] = -1;
                }
            }
        }
        boolean[][] visited = new boolean[R][C];
        markNearest(R, C,M,  out, q, visited);
        printMatrixInline(out);
        System.out.println();
    }

}

}

我的程序花了比预期的更多的时间。

请说明代码有什么问题。

Answer 1

基本上，在递归调用期间，如果遇到没有未访问邻居的单元格（这种情况发生），您将返回integer.max_value。从那开始事情就变糟了。

更重要的是，您的距离计算是错误的，因为您的递归调用是深度优先而不是广度优先。

这里有一些图画。您将按此顺序考虑邻居（因为x_pos和y_pos)

 ----> y
| 678
| 4.5
| 123
v
x

让我们看看在x单元格上开始时会发生什么（点表示带1的单元格：

0  0  0  .  .  0  .  0  0  0  .  0  0
0  0  .  .  .  0  0  .  0  0  .  .  .
0  0  .  0  0  .  0  .  .  .  .  0  .
.  0  0  .  0  0  0  0  0  .  0  0  0
.  0  0  0  0  x  0  .  0  .  .  .  0

以下是每次调用findnearth的递归深度：

11 12 13 14 17 16 17 16 19 20 21 .. .. 
 9 10 11 14 16 14 15 16 17 18 19 .. .. 
 8  7 11  7 15 14 13 15 15 15 19 .. .. 
 5  5  6  7  8  9 11 12 14 15 .. .. .. 
 5  4  3  2  1  0 10 11 13 14 .. .. .. 

和相应的(>0)返回值：

 3  2  1 .. ..  1 ..  1  2  1 .. .. .. 
 2  1 .. .. ..  1  1 ..  1  1 .. .. .. 
 1  1 ..  1  1 ..  1 .. .. .. .. .. .. 
..  1  1 ..  1  1  2  1  1 .. .. .. .. 
..  1  2  1  2  3  1 ..  1 .. .. .. ..

但只保留x单元格的一个，这里为3。但这是假的！只是因为你先往左走了。在这里，所有编号超过1的邻居都将从更深的递归中访问，并从外部调用的角度将其标记为不“安全”。这里的结果应该是2。

这里您还可以看到代码中的另一个问题，您为每个单元格重新计算了一堆（假）距离。对于较大的矩阵，您将使用O((n.m)**2)工作，而不是这里所必需的O(n.m)。