行列があり、各セルにはブールプロパティがあります。ブールプロパティがfalseに設定されているセルから開始して、サイクルを決定する必要があります。このサイクルには、ブールプロパティがtrueに設定されているセルのみが含まれている必要があります（開始セルを除く）。もう1つの条件は、サイクル内の2つの連続するセルが同じ行（または同じ列）にある必要があり、サイクル内の3つの連続するセルが同じ行（または同じ列）にある必要がないことです。実際には、あるセルから別のセルにジャンプできます。隣接するセルである必要はなく、同じ行または列にある必要があります。ありがとうございました。
1 に答える
0
更新：2つの隣接するセル間で移動する必要がないことを見逃しました。これにより、各ステップで可能な移動の数が増えますが、一般的な考え方は実際には変わりません。
最も簡単な実装は、おそらく深さ優先探索です。開始セルから開始して、考えられるすべての動きを調べます。最初の動きを除いて、考えられる動きは最大3つです。可能な移動ごとに、開始セルに再び到達するか、可能な移動がなくなるまで、同じことを再帰的に実行します。後者の場合、1つの動きを追跡し、残りが1つある場合は、次の可能性を試します。
この方向は次の移動には無効であるため、再帰呼び出しとともに最後の移動の方向を渡す必要があります。セルを数回訪問することが許可されていない場合は、訪問したセルも追跡する必要があり、追跡するときにそれらのマークを外します。セルを数回訪問することが許可されている場合は、サイクルを回避するために、以前にセルを訪問したときにセルを離れた方向を追跡する必要があります。
深さ優先探索の代わりに幅優先探索を使用すると、多数の部分的な解決策を記録しておくという犠牲を払って、解決策ではない長いパスを試すことを回避できます。*検索はこれをスピードアップする別のオプションかもしれません。
補足：セルを初めて訪問するときに他の動きを直接取ることができた可能性があるため、セルを数回訪問しても価値がない場合があります。例外は、セルに初めて入るときに許可されていない移動を行うことですが、そのようなパスが可能かどうかはわかりません。
于 2013-01-10T20:23:16.000 に答える