CODEWITHSUNDEEP
arraysalgorithm2ddistance
user2943215
user2943215

Reputation:

Distance between elements in 2D array

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 ?

Upvotes: 5

Views: 17705

Answers (6)

Sansei
Sansei

Reputation: 93

  • Use BFS by first adding all '1's into Q, and consider these cells as 0 in 'Cost' matrix (initialize other cells with n).
  • Then try to dequeue x (i.e. pair(i,j)) until Q is empty.
  • Update the neighbors in 'Cost' matrix with value 'x+1' only if is smaller than current value.
  • Add updated neighbors into Q.

Upvotes: 0

user797257
user797257

Reputation:

Because you didn't specify the language :) here's a parallel version of the algorithm in 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))

Upvotes: 2

Ari
Ari

Reputation: 2004

I liked this question, so I created a page online where you can try out solving it: http://www.learneroo.com/courses/29/nodes/221

The solution code is below, based on @manu-fatto's answer. The method minArray goes through the entire double array a few times, and each time it updates the minimum distance from each cell to a nearby 1 by picking the minimum value near it and adding 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);     
}

This method will calculate the minimum distance based on the current cell and its 4 neighbors:

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

The next two methods are for input/output (see link for full code):

private static void printArray(int[][] square) {
    //print the Array
}

public static void main(String[] args) {
    //get input into arrays
}
}

Upvotes: 2

Isaac
Isaac

Reputation: 11805

I know this may be just solving your homework, but I had to.

Here is an efficient way of solving your problem in JavaScript, I believe it is only O(n^2) (I'm a little rusty on O notation, and ignore the first loop which may be completed on data entry)

It works as follows

Get each elements position

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});
 }
}

Start looping through array

Grabbing the first entry and removing it. In c++ you should use a queue

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

Check if the distance hasn't already been set

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

Check if the x and y coordinates are within the bounds of the array

Add them to the end of the position array/queue, along with an extra distance unit

   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});

Display output

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

The full code:

<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>

Upvotes: 0

Duncan
Duncan

Reputation: 1024

You can iterate over the matrix and find the coordinates of all the 1's (x1, y1). Then for each position in the cell (x2, y2), for all (x1, y1) in your list, find the minimum |x2 - x1| + |y2 - y1| (the Manhattan distance since it's a grid).

Upvotes: 4

Emanuele Paolini
Emanuele Paolini

Reputation: 10162

Start with a matrix with 0 where the 1 are located and a large number (larger then any possible distance) on the other cells. Then iterate over your matrix. In every cell put the minimum between the current value and the minimum of values of adjacent cells plus one. Iterate until you don't need any update.

Upvotes: 0

Related Questions