logo标签列表

2D数组元素之间的距离

arraysalgorithm2ddistance
5

如何确定二维数组中1之间的距离。例如，我们有一个像这样的二维数组：

0 0 0 0
0 0 0 1
1 0 0 0
1 0 0 0

该算法需要输出每个元素距离最近的1的距离，如下所示：
2 3 2 1
1 2 1 0
0 1 2 1
0 1 2 2

我该怎么解决它？
这个问题是从某个编程挑战网站复制过来的吗？否则请展示一下你已经尝试过什么了！ - Rajat Shah
展示你所尝试过的内容。 - Maria Ines Parnisari
你也可以斜着走吗？ - rath
@r20rock 是的，这很具有挑战性，而且这只是其中的一部分。原始版本有点复杂。 - user2943215
我还没有尝试过任何真正的东西，也没有解决方案。 - user2943215
显示剩余3条评论
6个回答
4

你可以遍历这个矩阵并找到所有1的坐标(x1, y1)。接着，对于每个单元格的位置(x2, y2)，在你的列表中找到所有(x1, y1)，计算最小值：|x2 - x1| + |y2 - y1|（使用曼哈顿距离因为它是一个网格）。

路径是什么意思？ - user2943215
最小值不应该是 (x2 - x1) + (y2 - y1) 的绝对值吗？ - user2943215
我认为你的答案是正确的，谢谢！但让我们把它变得更加困难。给定一个数字K，您需要输出每个单元格到K个1的最小距离。因此，对于每个单元格，您只需找到最近的K个1，并输出最远的1的距离？我会编辑问题。 - user2943215
@user2943215 对距离列表进行排序并打印第k个元素。 - Smart Manoj
2
我很喜欢这个问题，所以我创建了一个在线页面，您可以在上面尝试解决它：http://www.learneroo.com/courses/29/nodes/221 下面是基于@manu-fatto的答案的解决方案代码。方法minArray多次遍历整个双倍数组，并每次通过选择其附近的最小值并添加1来更新每个单元格到附近1的最小距离。
import java.util.*;

class DistanceZ {   

static void minArray(int[][] square){
    int w = square.length;

    for(int times = 0; times<w; times++){
        for(int i =0; i<w; i++){
            for(int j=0;j<w;j++){
                square[i][j] = minCell(square, i, j);
            }
        }
    }       
    printArray(square);     
}

这个方法将基于当前单元格及其四个邻居计算最小距离：

static int minCell(int[][] square, int i, int j){
    //get the minimum of current cell and adjacent cells + 1.       
}

下面两种方法是关于输入/输出的（完整代码请参见链接）：
private static void printArray(int[][] square) {
    //print the Array
}

public static void main(String[] args) {
    //get input into arrays
}
}
+1，尽管我们已经使用过其他所有语言，但我喜欢这个问题，Clu正在使用的那种语言除外。 - Isaac
@Isaac 他在问题或标签中没有提到任何语言，不过现在我看到他在评论中提到了。无论如何，您可以在我链接的页面上使用不同的语言。 - Ari
@Ari，您能否用C语言发布您的代码或伪代码？我无法阅读您的语言，因此无法看出哪种方法更优。不管怎样，感谢您的工作。另外，请查看编辑后的问题。 - user2943215
@Clu，我添加了一些注释来解释代码。Java 代码与 C 代码并没有太大的区别。 - Ari
@Clu，抱歉，这里是完整的代码Gist链接：https://gist.github.com/arikrak/7404970 （您需要在该网站上注册才能进行挑战。） - Ari
显示剩余3条评论
2

因为你没有指定语言，这里提供一份Common Lisp版本的并行算法：

(ql:quickload :lparallel)
(defpackage :compute-distances (:use :cl :lparallel))
(in-package :compute-distances)

(defun positions (number matrix)
  (loop :for i :from 0 :below (array-dimension matrix 0)
     :nconc (loop :for j :from 0 :below (array-dimension matrix 1)
               :if (= number (aref matrix i j))
               :collect (cons i j))))

(defun find-neighbours (point points)
  (loop :with x := (car point) :and y := (cdr point)
     :for point :across points
     :unless (and (= x (car point)) (= y (cdr point)))
     :collect (let ((width (- x (car point)))
                    (height (- y (cdr point))))
                (sqrt (+ (* width width) (* height height))))))

(defun find-all-neighbours (number matrix)
  (let* ((positions (coerce (positions number matrix) 'vector))
         (*kernel* (make-kernel (length positions))))
    (pmap 'vector (lambda (point) (find-neighbours point number matrix))
          :parts (length positions) positions)))

(defparameter *test-matrix*
  (make-array '(4 4) :initial-contents
              '((0 0 0 0)
                (0 0 0 1)
                (1 0 0 0)
                (1 0 0 0))))

(find-all-neighbours 1 *test-matrix*)
;; #((3.1622777 3.6055512) (3.1622777 1.0) (3.6055512 1.0))
好吧，下次我应该注明语言:D 谢谢你的帮助。 - user2943215
0

我知道这可能只是解决你的作业，但我不得不这样做。

以下是使用JavaScript解决问题的高效方法，我相信它只有O(n^2)（我对O符号有点生疏，并忽略第一个循环，该循环可以在数据输入时完成）

它的工作原理如下：

获取每个元素的位置

for (var a=0,aa=arr.length; a<aa; a++) // this loop may be able to be done when data is read in
{
 result[a] = [];
 for (var b=0,bb=arr[a].length; b<bb; b++)
 {
  result[a][b] = -1;
  if(arr[a][b]==1)pos.push({x:a,y:b,dist:0});
 }
}

开始循环遍历数组

获取第一个条目并将其移除。在c++中，您应该使用队列

while(pos.length>0)
{
 var p = pos[0];
 pos.splice(0,1);

检查距离是否已经设置

 if(result[p.x][p.y]==-1)
 {

检查 x 和 y 坐标是否在数组的范围内

将它们添加到位置数组/队列的末尾，同时加上额外的距离单位。

   var x = p.x+dx[a];
   var y = p.y+dy[a];
    if(x>=0&&x<result.length&&y>=0&&y<result[p.x].length)pos.push({x:x,y:y,dist:p.dist+1});

显示输出

for (var a=0,aa=arr.length; a<aa; a++)
{
  console.log(result[a]);
}

完整代码：

<script>
var arr = [
[0,0,0,0],
[0,0,0,1],
[1,0,0,0],
[1,0,0,0]];
var result = [];
var pos = [];

for (var a=0,aa=arr.length; a<aa; a++) // this loop may be able to be done when data is read in
{
 result[a] = [];
 for (var b=0,bb=arr[a].length; b<bb; b++)
 {
  result[a][b] = -1;
  if(arr[a][b]==1)pos.push({x:a,y:b,dist:0});
 }
}
var dx = [-1,0,0,1];
var dy = [0,1,-1,0];

while(pos.length>0)
{
 var p = pos[0];
 pos.splice(0,1);
 if(result[p.x][p.y]==-1)
 {
  result[p.x][p.y] = p.dist;
  for(var a=0; a<4; a++)
  {
   var x = p.x+dx[a];
   var y = p.y+dy[a];
   if(x>=0&&x<result.length&&y>=0&&y<result[p.x].length)pos.push({x:x,y:y,dist:p.dist+1});
  }
 }
}
for (var a=0,aa=arr.length; a<aa; a++)
{
  console.log(result[a]);
}

</script>
0
  • 使用BFS，首先将所有的“1”添加到队列Q中，并将这些单元格视为“Cost”矩阵中的0（将其他单元格初始化为n）。
  • 然后尝试出队x（即pair（i，j）），直到Q为空为止。
  • 仅当更新后的值小于当前值时，才在“Cost”矩阵中更新邻居的值为“x + 1”。
  • 将更新后的邻居添加到Q中。
0

从一个矩阵开始，其中0表示1的位置，其他单元格上有一个大数（大于任何可能的距离）。然后迭代您的矩阵。在每个单元格中，将当前值和相邻单元格值的最小值加一放入其中。迭代直到不需要更新为止。

那么，对于每个单元格，我都必须遍历整个矩阵吗？ - user2943215
不完全正确。你将不得不迭代整个矩阵n次，其中n是最终存储在最隔离的单元格中的“距离”。 - Penguino
在每个单元格中，将当前值和相邻单元格值的最小值加一放入其中。我不太理解这部分内容。 - user2943215
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接