java - 具有 1 的最近单元格的距离
问题描述
给定一个大小为 N x 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();
}
}
}
我的程序花费了比预期更多的时间。
请提出代码有什么问题。
解决方案
基本上,在递归调用期间,如果遇到没有未访问邻居的单元格(发生这种情况),您将返回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
以下是每次调用的递归深度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) 返回值:
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)
必要的工作。
推荐阅读
- node.js - 使用 express 框架 js 将图像插入 SQL Server
- jquery - 使用ajax悬停和删除操作的最后一个唯一索引?
- pvlib - pvlib.inverter.fit_sandia 返回零 C1、C2、C3 系数
- c# - F# 错误:无法引用值和 If Else 语句
- expression - 如何在 OCaml 上使用 fold 编写 contains_var 函数?
- c - 将标准输入流式传输到套接字
- ruby-on-rails - Rails 6 仅在参数存在时更新属性
- asp.net-core - 将代币用于测验系统好吗?
- javascript - 将json作为body和另一个对象作为参数传递给spring控制器
- javascript - 具有范围选择的角度日期选择器,如 vue.js