プログラミングの本の中で、解決できない次の問題に遭遇しました。
nxm グリッドが与えられた場合、このグリッドを 3x1 および 1x3 ブロックで埋めることができる方法の数を見つける再帰アルゴリズムを作成します。
3 x M グリッドの私のロジック:
グリッドのサイド M を埋めるために使用できるブロックの組み合わせの数を見つけます。
上記の質問を解決するためにロジックを変更する方法がわかりません。
誰かアドバイスしてくれませんか?ありがとう。
プログラミングの本の中で、解決できない次の問題に遭遇しました。
nxm グリッドが与えられた場合、このグリッドを 3x1 および 1x3 ブロックで埋めることができる方法の数を見つける再帰アルゴリズムを作成します。
3 x M グリッドの私のロジック:
グリッドのサイド M を埋めるために使用できるブロックの組み合わせの数を見つけます。
上記の質問を解決するためにロジックを変更する方法がわかりません。
誰かアドバイスしてくれませんか?ありがとう。
を左上position
隅とし、その後はグリッドの最初の未充填スロット (左から右、次に上から下) とします。にブロックを配置するには、最大 2 つの方法がありますpostion
。に 1x3 の水平ブロックを配置してみposition
て、残りのグリッドで再帰関数を呼び出します。に 3x1 の垂直ブロックを配置して、position
その上で再帰関数を呼び出してみてください。ブロックを配置する合法的な方法がない場合 (たとえば、最後に 2x2 の正方形しか残っていないなど)、プログラムのこのブランチは解決策を見つけることができませんでした。これは、グリッドを 3x1 ブロックで埋める必要があるためです。
あなたのロジックは再帰的ではありません-それは組み合わせアプローチであり、数えようとしています。しかし、グリッドが大きくない限り、コンピューターには実際にすべての組み合わせを試すのに十分なメモリがあります。このアプローチを、本で再帰的に解決される他の問題に関連付けることができれば、それは素晴らしいことです。
メソッドシグネチャのアイデアは次のとおりです
int blockFillings(boolean[][] grid, int posx, int posy)