具有1的最近像元的距离 [英] Distance of nearest cell having 1
问题描述
给出大小为N x M的二进制矩阵.任务是为每个像元查找矩阵中最接近1的距离.距离计算为| i1 – i2 |+ | j1 – j2 |，其中i1，j1是当前单元格的行号和列号，而i2，j2是值1的最近单元格的行号和列号.
Given a binary matrix of size N x M. The task is to find the distance of nearest 1 in the matrix for each cell. The distance is calculated as |i1 – i2| + |j1 – j2|, where i1, j1 are the row number and column number of the current cell and i2, j2 are the row number and column number of the nearest cell having value 1.
输入:输入的第一行是一个整数T，它表示测试用例的数量.然后是T测试用例.每个测试用例包含2行.每个测试用例的第一行包含两个整数M和N，它们表示矩阵的行数和列数.然后在下一行是矩阵(mat)的N * M个空格分隔的值.
Input: The first line of input is an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of 2 lines . The first line of each test case contains two integers M and N denoting the number of rows and columns of matrix . Then in the next line are N*M space separated values of the matrix (mat) .
这是我的代码:
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();
}
}
}
我的程序花了比预期更多的时间.
My program took more time than expected.
请提示代码出了什么问题.
Please suggest what is wrong with the code.
推荐答案
基本上，在递归调用过程中，如果遇到未访问邻居的 no 单元格(会发生这种情况)，您将返回Integer.MAX_VALUE .从那里开始，情况变糟了.
Basically, during you recursive calls, if you encounter a cell with no unvisited neighbor (which happens) you will return Integer.MAX_VALUE. From there things go bad.
更重要的是，您的距离计算是错误的，因为您的递归调用是深度优先而不是宽度优先.
More importantly, your distance calculation is wrong because your recursive calls are depth first instead of breadth first.
这里有一些图纸.您正在按此顺序考虑邻居(因为 x_pos 和 y_pos )
Here with some drawings. You are considering the neighbors in this order (because of x_pos and y_pos)
----> y
| 678
| 4.5
| 123
v
x
让我们看看从x单元格开始(点号为1的单元格的点:
Let's see what happens when you start on the x cell (dots for cells with a one:
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
以下是每次调用 findNearest 的递归深度:
Here are the recursive depth of each call to findNearest:
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)返回值:
and the corresponding (>0) return values:
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.
But keep only the one for the x cell, here 3. But it's false!
It's just because you went left first. Here all neighbors numbered more than 1 are visited from deeper recursion, and marked as not "safe" from the point of view of your outer call. The result here should be 2.
您还可以在这里在代码中看到另一个问题，您需要为每个单元格重新计算一堆(假)距离.对于更大的矩阵，您将执行 O((n.m)** 2)的工作，而不是此处所需的 O(n.m).
You can also see here another problem in your code, you recompute for each cell a bunch of (false) distances.
For a bigger matrix, you'll do O((n.m)**2) work instead of the O(n.m) necessary here.
这篇关于具有1的最近像元的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
