私は BFS の問題を解決していました。隣接リストを使用して C で BFS アルゴを実装することができましたが、この問題で立ち往生していました。迷路の始点から終点まで移動できるかどうかを判断する必要があります。迷路。セルには 0 または 1 が含まれます。値 1 を含むセルを通過することはできず、2 つのセル間の移動は、それらが共通のエッジを共有している場合にのみ可能であるという制限が与えられます。では、隣接リストを使用せずにここで BFS を直接実装する方法は?
1 に答える
2
BFS を行うために、グラフを隣接リストとして明示的に表現する必要はありません。各セルから、その 4 つの潜在的な隣接セル( 、、および)(x,y)がわかります。それらのいずれかがテーブルから落ちて、隣人ではない可能性があるためです。ここで、各頂点を整数のペア (その座標) で識別し、ペアをキューにプッシュします。キューからポップするときは、上で述べたことを使用して 4 つの可能なネイバーにアクセスします。(x-1, y)(x, y-1)(x+1, y)(x, y+1)potential
これがあなたの助けになることを願っています - 私は完全なコードを提供することができますが、あなた自身でそれを書く方が良いです.
于 2013-09-26T12:20:08.747 に答える