1

ブール値の2D配列を上境界から下境界までトラバースし、完全にtrue値で構成されるパスを決定する必要があります。この時点で、私はさまざまなテクニックを試しましたが、何も進歩していません。誰かがここで私を助けてくれますか？

次に例を示します。

false true  true  false false false
false true  false false false false
false true  true  false false false
false false true  false false false

true境界に沿って値を決定する方法を見つけてから、値のパスをトラバースする方法を見つける必要がありtrueます。

#..###
#.####
#..###
##.###

この時点でアルゴリズムを開始しました。列をトラバースしてtrue値を検索し、行を1つずつインクリメントしてから最後の行を検索することを考えましたが、最初と最後の列を検索する方法がわかりません。

true問題の最初の部分は、境界に沿った値の位置を決定することです。2番目の部分は、true値のパスを見つけて、それらの座標を記録することです。

4

2 に答える 2

3

これは、簡単な試行錯誤のアルゴリズムで解決できます。上から下への要件は、配列の一番上の行から開始する必要があることがわかっているので便利です。そのため、その1つの行でtrue開始する値を検索するだけです。

を見つけたらtrue、隣接するセルを確認します。（正確に隣接するセルは、対角線がカウントされるかどうか、およびパスがシンクの下のトラップパイプのように上向きに曲がることができるかどうかによって異なります。）

ここに画像の説明を入力してください

（ウィキペディアからの画像）

を含む別のセルを見つけた場合true、そのセルが「現在の」セルになり、その隣接セルを調べます。true最後の行のセルに到達するまでこれを続けます。または、隣接セルが見つからない場合はtrue、前のセルに戻って隣接セルを続行します。

これを行う1つの方法は、再帰とごくわずかなコードを使用します。次のようなことをするだけです

// pseudocode only
for(Cell foo : all cells in top row)
    checkCell(foo);

boolean checkCell(Cell current) {
    if(current == false)
        return false;

    if(current == true && current.isInLastRow == true)
        return true;

    // if we reach here, the cell is true but we're not done
    for(Cell foo : all valid neighbors of this cell except the "parent")
        return checkCell(foo);
}

別の方法はより多くのメモリを使用しますが、より効率的です。元の配列と同じサイズの2番目の配列を作成します。元の配列からセルをテストするときは、新しい配列で対応するセルにマークを付けます。次に、ネイバーをテストするときに、新しいアレイをチェックして、特定のネイバーにすでにアクセスしたことがあるかどうかを確認します。持っている場合は、それをスキップしてください。成功につながることはありません（可能であれば、すでに完了して戻ってきているので、これを知っています）。trueこれにより、配列に次のように多数の値が隣り合って含まれている場合に、時間を大幅に節約できます。

F T T T F
F T T T F
F T T T F
F T T T F
F T T T F

編集：
パス内のセルの座標を記録する必要があるという更新コメントを見逃しました。問題ありません。これまでに行ったことを記録するオブジェクトのスタックを作成するだけです。間違った道をたどってしまった場合は、「レベルを上げる」たびにスタックから1回ポップするだけです。Point

于 2012-11-23T17:11:06.027 に答える
1

それをグラフに変換して、パスファインディングアルゴリズムを実行できます。

すべての行列エントリをグラフ上のノードに変換します。trueマトリックスのに配置されたノードごとに、値[i,j]を使用して最も近い4つの隣接エントリのすべてに接続しtrueます。つまり、そのようなエントリがtrueの場合は常にそのエントリ[i+/-1, j]に接続します。[i, j+/-1]これらはすべて、グラフ上の唯一のエッジです。次に、上部の境界に配置されたすべてのノードでDijkstraアルゴリズムhttp://en.wikipedia.org/wiki/Dijkstra%27s_algorithmを実行します。trueそのようなパスがあるときはいつでも、各ノードペア間の最短パスを返しますtrue。

于 2012-11-23T18:40:58.627 に答える