How can I determine the distance between 1's in a 2D array. For example, we have a 2D array like this:
0 0 0 0
0 0 0 1
1 0 0 0
1 0 0 0
The algorithm has to output the distance from each element to the nearest 1. Like this:
2 3 2 1
1 2 1 0
0 1 2 1
0 1 2 2
How can I solve it ?
您可以遍历矩阵并找到所有 1 (x1, y1) 的坐标。然后对于单元格 (x2, y2) 中的每个位置，对于列表中的所有 (x1, y1)，找到最小值 |x2 - x1| + |y2 - y1| （曼哈顿距离，因为它是一个网格）。
因为您没有指定语言:) 这是 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))
我喜欢这个问题，所以我在网上创建了一个页面，您可以尝试解决它： 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);
}
此方法将根据当前单元格及其 4 个邻居计算最小距离：
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
}
}
我知道这可能只是解决你的作业，但我不得不这样做。
这是用 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 的矩阵开始，其中 1 所在的位置和其他单元格上的一个大数字（大于任何可能的距离）。然后迭代你的矩阵。在每个单元格中，将当前值与相邻单元格的最小值加一之间的最小值。迭代直到您不需要任何更新。