c - バックトラック再帰を使用した自己回避歩行

Question

与えられた：グリッドm×n
交差点が1つだけで、バックトラックと再帰を使用して右上隅で終了するすべてのパスを列挙する必要があります！？助言がありますか 。？
自己回避歩行

Answer 1

非再帰的な方法は、前の位置とその位置での決定を必要とする情報のスタックを保持することです。決定が下されるたびに、保存する必要のある情報をスタックの一番上にプッシュします。

次に、前方検索で問題が見つかると、スタックがポップされ、最新の決定ポイントに戻って別の決定が行われます。最終的には、成功するか、すべての可能なパスを不可能として排除します。

再帰的なソリューションの場合も同じですが、情報をスタックにプッシュする代わりに、再帰的な呼び出しで決定した後に新しい位置を渡します。再帰呼び出しが失敗を返す場合は、現在の位置で次の可能な決定を試みます。現在の位置で選択肢がなくなった場合は、失敗を上のレベルに戻します。再帰呼び出しが成功を返す場合にのみ、このレベルは成功を返します。

この場合も、最終的にはコールチェーン全体で成功が返されるか、すべての可能なパスが削除されます。

また、これは宿題であるため、あるレベルから次のレベルに渡す必要のある情報と、最終的な成功パスをアプリケーションに返す方法を自分で決定する必要があります。

必要なすべての新しいアイデアは、上記の段落にあります。実装はあなた次第です。

-ジェシー