algorithm - 正方形の中心から端までの経路を数える

Question

いくつかの n に対してサイズ (2n+1)x(2n+1) の正方形、つまり奇数辺の長さの正方形があるとします。
中央のセルから始めて、いいえを数えることに興味があります。任意のエッジ セルに到達する方法 (次の図に示すように)。
重複しないパスのみが許可されます。つまり、セルが既にアクセスされている場合、そのセルを再度アクセスすることはできません。

次の図は、辺 9(n=4) の正方形と長さ 5 の 2 つの可能なパスを示しています。

すべてのパスの長さの範囲は [n から (2n-1)^2+1 ] になると思います
。長さのパスの数:
1 - 0
2 - 0
3 - 0
4 - 4
5 - 32
6 - ...?
しかし、パスの長さが長くなるにつれて、すべての可能性を解き明かすことはできないようです。ここで対称性が機能することは知っていますが、すべてのパスを数えるための構造化された方法はありますか?

ありがとう、

Answer 1

正方形のボードの中心から始まり、境界で終わるパスを見つけるには、微調整された DFS (深さ優先検索) を使用して、既に訪れたタイルを保存し、再びそれらを踏まないようにすることができます。

ボードには確かに多くの対称性があります。次のことに注意するだけで、検索されたパスの数を 4 で割ることができます。

• U中心から、 p、Down、Left、ightに行くことができますR
• Upを開始するすべてのパスは、 Down、Left、Rightを開始する他のすべてのパスを回転によって生成します。

これを行うと、次のことに気付くことで、さらに先に進むことができます。

• あなたが行ったらU、あなたは行くことができますU、LまたはR
• 行ったときに生成されるすべてのパスは、ミラー対称Lで行ったときに生成されるものと同じです。R

正方形の境界に到達するまで、これを数回繰り返すことができます。go で始まるパスの全量は次のようにUなります。

• U-U-U-U(1 つのパス)
• で始まる 2 回のパスU-U-U-L
• で始まる 2 回のパスU-U-L
• で始まる 2 回のパスU-L

それらを数えると、4 を掛けることでパスの全量が得られます。