私は最近、就職インタビューのために登場しました。一般的なRAT IN A MAZE PROBLEMには、開いているパスと壁にそれぞれ0と1を含む2次元配列で表される迷路があり、最短経路。バックトラック - 「迷路のラット」のこの変種を解決するにはどうすればよいですか？
バックトラックを使用して問題を解決し、可能なすべてのパスも印刷しました。
しかし、インタビュアーは靭性レベルを高め、Kがユーザーによって入力された "K"個の壁をトリップすることができる新しい状態で同じ質問を解決するように頼んだ。
今私はたくさん試しましたが、K壁をトリップすることが許されていれば最短経路を見つける方法を見つけられませんでした。私はそれがダイナミックプログラミングで解決できるかどうかは考えましたが、
また、面接者は解決策を明らかにしませんでした。 誰もこの問題の解決方法を説明できますか？
breadth-first searchを使用して解決できます。
上記にリンクされている基本的なBFSアルゴリズムを読むことから始めてみましょう。
wallsを呼び出します。開始セルを含むキューから開始します。
出発細胞のwallsを0とする。
現在のセルをキューの最初の要素（削除する要素）と繰り返し設定します。
現在のセルがターゲットセルの場合、パスをプリントアウトすると完了です。現在のセルが壁がある場合
、何もしない、current.walls > K場合1.
でcurrent.wallsを高めます。その後、セット（壁やオープンセル）
neighbour.wallsが（新しいパスが少ない壁を有するという意味）初期化（我々の前に存在していないという意味）またはcurrent.walls < neighbour.wallsされていない場合は、
：各隣人のために
neighbour.wall = current.wallsを追加し、neighbourをキューに追加します。
実際に私たちがそこにから来た（と、それはwallsだ）のセルにそのwallsで任意のセルをマップするマップを作成し、パスをプリントアウトできるようにするには。 Kの値が小さい場合は、パス上の以前のセルを上書きできるため、セルを前のセルにマップするだけでは機能しません。
パス全体を保存することもできますが、効率が大幅に低下します。
時間複雑度はO(rows*columns*K)であり、空間複雑度はO(rows*columns)です。
ここでは複雑の多くは、このようなシナリオに対処する必要の結果、次のとおりです。
（あなたは、より大きなグリッドのこの一部では想像することができます）
Kが十分に大きい場合は、2つの壁（緑色のパス）を交差させ、2つの移動で右上のセルに到達できます。
Kが十分でない場合は、4つの動きが必要です（青色のパス）。
したがって、私たちは定期的なBFSを実行しますが、各セルの壁の数も把握していますので、移動した後に右上のセルに到達すると、 2つの壁（現在の0の代わりに）を横切っているので、2つの壁を使用するパスがあまりにも多くの壁を通過する必要がある場合には、そこから進みます。
"旅行"の壁では、壁を通って移動する、または壁を取り除くことを意味しますか？ – Dukeling
これはDijkstraで解決できる変種で、どのノードもどの壁が削除されたかを保存します。 –