多項式時間で解く方法迷路パズルのラット？

Question

私は最近のインタビューでthis questionを頼まれた。

A迷路は、ソースブロックが 上部左端のブロック、すなわち、迷路[0] [0]と先であるブロックのN * Nのバイナリ行列として与えられます。ブロックは 右下のブロック、すなわち迷路[N-1] [N-1]である。ラットはソース から出発し、目的地に到着しなければならない。ラットは、 の順方向と下方向の2つの方向にのみ移動できます。 （先進問題では4）。迷路行列では、0 はブロックがデッドエンドであることを意味し、1はブロックがソースからデスティネーションへのパスで使用できることを意味します。

私の答えはバックトラックを使用しているリンクに記載されたものでした。リンクから高レベルの擬似コード：

If destination is reached 
    print the solution matrix 
Else 
    a) Mark current cell in solution matrix as 1. 
    b) Move forward in horizontal direction and recursively check if this 
     move leads to a solution. 
    c) If the move chosen in the above step doesn't lead to a solution 
     then move down and check if this move leads to a solution. 
    d) If none of the above solutions work then unmark this cell as 0 
     (BACKTRACK) and return false. 

インタビュアーは私の応答によってかなり驚いた、と明らかに多項式時間ソリューションを期待していました。

この問題の多項式時間解が存在しますか？

Answer 1

これは、BFSを使用して線形時間で解くことができます。

問題は実際にはすべてのセルが頂点であり、セルからの可能な移動がエッジであるグラフです。ソースから目的地までの最短経路を探しています。これは正確にBFSが行うものです。生成するには

（これは4つの許可方向を有する、より複雑な問題のためにかかわらず、真実ではありません。唯一の「ダウン」と認め、「右」と単純化の問題で、有効なパスが同じ長さを持っていることに注意してください）

実際のパスでは、探索された各ノードの親を「記憶」することによってパスを追跡する必要があります。これは質問で議論されます：How can I find the actual path found by BFS?