矩阵中最近的非零元素
closest nonzero element in a matrix
维度为 n*n 的矩阵仅包含零和一作为元素。编写伪代码以最小复杂度为每个元素找到最接近的非零元素。
• 距离为欧氏距离
输入矩阵
0 0 0
0 0 0
0 0 1
输出
平方（8）平方（5）2
平方（5）平方（2）1
2 1 0
我知道蛮力法但我试图应用一个更快的解决方案并将矩阵视为图形然后应用最短路径algo.Am我走的方向正确吗？我在思考方面几乎不需要帮助
编辑：问题也给出了提示
提示
• 首先针对每一列分别求解一个维度。
• 然后将结果用于二维问题。
如果您需要最有效的算法来完成此类任务，您可以进行前提条件计算：
- 读取矩阵 ( O(n*n) )
- 为每个最靠近左边的单元格查找 1 (O(n*n)) 存储在数组 A
- 为每个单元格找到最右边的 1 (O(n*n)) 存储 int 数组 B
- 当您 select 元素（例如 dist(2,3)）从 A && B 数组中找到最小值时（例如 min(A[2][3], B[2][3])） ;
在这种情况下，创建总渐近：O(3*N*N)，内存：3*N*N
但是对于访问，您会将其减少到 O(1)
P.S。初始化资源可以减少到 O(N) mem: N 结合步骤（例如简单的结合第一步和第二步），但是你自己做:)
P.P.S。
哦，我有点太苛刻了，没有想到距离是欧几里得。在这种情况下，您可以按照我之前的建议进行操作。但是这个初始化的渐近将是 O(NNN)，但你只能将它改进为 O(NNlog(N))使用像 bfs 这样的图形算法：
- 输入矩阵
- 创建额外的数组 dist 并用 inf(smth like 1*1000*1000) 填充它
- 通过它找到 1
- 在主要方向开始 bfs
- 在 dist 数组中存储旧值和新计算的最小值 (dist[i][j] = min(dist[i][j], calc_dist(i,j, i_1 , j_1))
而且这个算法还可以改进一点点；
所以减少访问访问时间的主要想法是预先计算并尽可能存储它们。
首先 - 当比较从直角坐标获取的距离时，永远不要真正比较它们，而是比较它们的正方形，算作 dx^2+dy^2。你不需要在 sqrt 上浪费时间！
- 因此，检查距 {0,1,2,...,（最远
角落）}。每一个：
- 在内循环中寻找所有dx>0 & dy>0，例如dx^2+dy^2 = SD。
- 在最里面的循环中组合-+符号为dx,dy。
- 将 dx 和 dy 添加到源坐标。
- 检查结果单元格是否在矩阵内部
- 检查结果单元格的内容是否为 0。
显然，第二个循环是最复杂的。我会帮助 table f(a,b)=a^2+b^2 并在其中寻找 SD，使用 table 是单调的。
因此，对于大距离，复杂度将为 O(n^2)，并且该算法也适用于最近的距离。
我相信您正在寻找的是给定矩阵的欧氏距离变换。在 http://cs.brown.edu/~pff/dt/ 有一篇论文和一个实现（计算图像的欧几里得距离变换）。他们声称算法的渐近 运行 时间是 O(dN)，其中 d 是维度（在你的情况下是 d=2），N 是点数（ N = n^2 在你的例子中，n 是矩阵的大小）。
维度为 n*n 的矩阵仅包含零和一作为元素。编写伪代码以最小复杂度为每个元素找到最接近的非零元素。
• 距离为欧氏距离
输入矩阵
0 0 0
0 0 0
0 0 1
输出
平方（8）平方（5）2
平方（5）平方（2）1
2 1 0
我知道蛮力法但我试图应用一个更快的解决方案并将矩阵视为图形然后应用最短路径algo.Am我走的方向正确吗？我在思考方面几乎不需要帮助
编辑：问题也给出了提示
提示
• 首先针对每一列分别求解一个维度。 • 然后将结果用于二维问题。
如果您需要最有效的算法来完成此类任务，您可以进行前提条件计算：
- 读取矩阵 ( O(n*n) )
- 为每个最靠近左边的单元格查找 1 (O(n*n)) 存储在数组 A
- 为每个单元格找到最右边的 1 (O(n*n)) 存储 int 数组 B
- 当您 select 元素（例如 dist(2,3)）从 A && B 数组中找到最小值时（例如 min(A[2][3], B[2][3])） ;
在这种情况下，创建总渐近：O(3*N*N)，内存：3*N*N 但是对于访问，您会将其减少到 O(1)
P.S。初始化资源可以减少到 O(N) mem: N 结合步骤（例如简单的结合第一步和第二步），但是你自己做:)
P.P.S。 哦，我有点太苛刻了，没有想到距离是欧几里得。在这种情况下，您可以按照我之前的建议进行操作。但是这个初始化的渐近将是 O(NNN)，但你只能将它改进为 O(NNlog(N))使用像 bfs 这样的图形算法：
- 输入矩阵
- 创建额外的数组 dist 并用 inf(smth like 1*1000*1000) 填充它
- 通过它找到 1
- 在主要方向开始 bfs
- 在 dist 数组中存储旧值和新计算的最小值 (dist[i][j] = min(dist[i][j], calc_dist(i,j, i_1 , j_1))
而且这个算法还可以改进一点点；
所以减少访问访问时间的主要想法是预先计算并尽可能存储它们。
首先 - 当比较从直角坐标获取的距离时，永远不要真正比较它们，而是比较它们的正方形，算作 dx^2+dy^2。你不需要在 sqrt 上浪费时间！
- 因此，检查距 {0,1,2,...,（最远 角落）}。每一个：
- 在内循环中寻找所有dx>0 & dy>0，例如dx^2+dy^2 = SD。
- 在最里面的循环中组合-+符号为dx,dy。
- 将 dx 和 dy 添加到源坐标。
- 检查结果单元格是否在矩阵内部
- 检查结果单元格的内容是否为 0。
显然，第二个循环是最复杂的。我会帮助 table f(a,b)=a^2+b^2 并在其中寻找 SD，使用 table 是单调的。
因此，对于大距离，复杂度将为 O(n^2)，并且该算法也适用于最近的距离。
我相信您正在寻找的是给定矩阵的欧氏距离变换。在 http://cs.brown.edu/~pff/dt/ 有一篇论文和一个实现（计算图像的欧几里得距离变换）。他们声称算法的渐近 运行 时间是 O(dN)，其中 d 是维度（在你的情况下是 d=2），N 是点数（ N = n^2 在你的例子中，n 是矩阵的大小）。