arrays - 2D 配列の要素間の距離

Question

2D 配列の 1 間の距離をどのように決定できますか。たとえば、次のような 2D 配列があります。

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

どうすれば解決できますか？

Answer 1

マトリックスを反復処理して、すべての 1 の座標 (x1、y1) を見つけることができます。次に、セル内の各位置 (x2, y2) について、リスト内のすべての (x1, y1) について、最小 |x2 - x1| を見つけます。+ |y2 - y1| (グリッドなのでマンハッタン距離)。

Answer 2

私はこの質問が気に入ったので、オンラインで解決できるページを作成しました: http://www.learneroo.com/courses/29/nodes/221

@ manu-fattoの回答に基づいたソリューションコードは以下のとおりです。このメソッドminArrayは double 配列全体を数回調べ、そのたびに各セルから近くの 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.       
}

次の 2 つのメソッドは入力/出力用です (完全なコードについてはリンクを参照してください)。

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

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

Answer 3

1 が配置されている場所が 0 で、他のセルが大きな数 (考えられる距離よりも大きい) の行列から始めます。次に、マトリックスを反復処理します。すべてのセルに、現在の値と隣接するセルの値の最小値に 1 を加えた値の間の最小値を入力します。更新が不要になるまで繰り返します。

Answer 4

• 最初にすべての '1' を Q に追加して BFS を使用し、これらのセルを 'Cost' マトリックスで 0 と見なします (他のセルを n で初期化します)。
• 次に、Q が空になるまで x (つまり、pair(i,j)) のキューからの取り出しを試みます。
• 現在の値よりも小さい場合にのみ、値 'x+1' で 'Cost' マトリックスの近傍を更新します。
• 更新された隣人を Q に追加します。