1

私はグリッドについて考えています。グリッド内の「#」は道が塞がれていることを表し、「.」(引用符なしのドット) は道があることを表しているとします。したがって、A がグリッド内にある場合、A は見つけたときに中を歩くことができます。方法 (.) 例:

#######
##A####
##.#.##
##.#.##
##...##
#######

上記の例の場合、A は道を見つけ、下の図のように別の場所に到達します。

#######
##.####
##.#A##
##.#.##
##...##
#######

この問題をグラフとして考えている場合、このグリッドをグラフとしてどのように表現しますか? これを隣接リストとして表す方法は? BFS のみを学習したばかりのグラフを作成するのは初めてです。簡単な言葉で答えてください

4

1 に答える 1

1

各セルには、隣接する 4 つのセルすべてへのエッジがあります。したがって、すべてのセルは、隣接する 4 つのセルすべての隣接リストに表示されます。

実際には、グラフを明示的に構築する必要はなく、グリッド自体で作業することができます。特定のノードを表すには、該当するセルの座標を使用するだけでよく、隣のノードに移動するには、x / y を 1 ずつ増減できます。

これが十分に明確であることを願っています。

于 2013-07-31T12:18:05.703 に答える