如何确定二维数组中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
我该怎么解决它?
如何确定二维数组中1之间的距离。例如,我们有一个像这样的二维数组:
0 0 0 0
0 0 0 1
1 0 0 0
1 0 0 0
2 3 2 1
1 2 1 0
0 1 2 1
0 1 2 2
你可以遍历这个矩阵并找到所有1的坐标(x1, y1)。接着,对于每个单元格的位置(x2, y2),在你的列表中找到所有(x1, y1),计算最小值:|x2 - x1| + |y2 - y1|(使用曼哈顿距离因为它是一个网格)。
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
}
}
因为你没有指定语言,这里提供一份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))
我知道这可能只是解决你的作业,但我不得不这样做。
以下是使用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的位置,其他单元格上有一个大数(大于任何可能的距离)。然后迭代您的矩阵。在每个单元格中,将当前值和相邻单元格值的最小值加一放入其中。迭代直到不需要更新为止。