最近、私は述べた問題に遭遇しました。
*,.,Cの迷路を想定します。 *は壁面を表し、./Cが許されます。 Cと記されている点は1つだけです。ボットが許可されたポイントのいずれかに立つと、ボットが許可されたポイントから開始する場合、少なくとも1回はCを通過する一連のコマンド（たとえば、LDDRUまたはLLLRRDUなど）が存在します。
例：すべてのスタートポイントから解決した迷路
******
*.C..*
**.***
*....*
******
コマンド：RLLURUU
今、私は（最短経路のため）DFS/BFSを使って迷路を解決する方法を知っています。しかし、誰かがこのような問題をどのように進めるかについてのヒントを提供することができますか？
EDIT：次の移動が壁/外の迷路にある場合、無視されます。そして通常通りLは左Rです。右はUです。Dは下がっています。
この問題は、有限オートマトンのsynchronizing wordsまたはリセットシーケンスのコンセプトに関連しています。
このオートマトンでは、すべての状態をC状態にして同期ワードに接続するシーケンスを探しています。同期語を見つけるためのアルゴリズムは数多くあり、それらのうちのいずれかをこの特定の問題を解決するように適合させることができる。 1つの選択肢はbuild the power automaton from the original automatonで、スタート状態からC状態へのパスを探すことができます。これは理論的に最適なバージョンのコメントであり、仮想ロボットを一緒に崩壊させることについて話しています。
"力のオートマトンを構築する" - それはアクセス可能なノードだけを構築する場合でも指数関数的です。何か速い？私も最短の同期語は必要ありません。 –
あなたはモバイル版のwikipediaにリンクしました。修正してください。 –
@JanDvorakああ、申し訳ありませんが、私はあなたが最短の解決策を必要としなかったことを認識しませんでした。パワーオートマトンの構築は、任意のオートマトンに対して最悪のケース指数関数ですが、このカスの特定のオートマトンが実際にそれを引き起こすかどうかはわかりません。私はそのことについて考える必要があります。最悪の場合の多項式時間であることが知られている他のアプローチがありますが、あまりよく知られていません。 – templatetypedef
最も遠くに移動できるのは3ステップです。例えば、 LLLでは、グリッド内の3つの位置にしか配置できません。別のRの後に、あなたは垂直廊下の3つの位置にいることができます。あなたはUUの後にCを渡したことを確信しています。一般的に、あなたができるポジションの数を減らし、あなたの可能なすべてのロボットを追跡し、 「壁があれば、ロボットは動かない」というルール。 2つの可能なロボットが同じ正方形に終わるたびに、それらのうちの1つを取り除く。 – m69
@ m69、お返事ありがとうございます。しかし、もっと明確にするために、与えられた例を使用し、答えに到着するあなたの論理を説明することができます....ありがとう！ – yobro97
3行に9つの可能な位置があります。 LLLの後では、ロボットはその行の一番左の位置にあるので、今度は3つの可能な姿勢しか持たない。別のRの後で、3つのロボットは第2左の位置（垂直回廊）にある。 UUの後ではすべてがC上に終わるでしょう。 – m69