C++で長方形を最小数の正方形でタイリングする方法

n × m のサイズの長方形が与えられたとき、その長方形を隙間なく覆うために必要な「整数の辺を持つ正方形」の最小個数を求める問題を考えてみましょう。

たとえば、入力が n = 2、m = 3 の場合は次のようになります。

この場合の出力は 3 です。2 × 3 の長方形を完全に埋めるには、3つの正方形ブロックが必要になるためです。

アルゴリズムの流れ

この問題は、深さ優先探索（DFS）をベースに、枝刈りとメモ化を組み合わせることで効率的に解くことができます。各時点での盤面の状態を「各列に積み上がった高さ」として管理し、最も低い列に正方形を置いていくのがポイントです。具体的な手順は以下の通りです。

• 探索済みの状態を記録するためのマップ s を用意します
• 答えを格納する変数 res を無限大（inf）で初期化します
• dfs() 関数を定義します。引数は n、m、各列の高さを保持する配列 h、これまでに置いた正方形の個数 cnt です
• cnt >= res の場合、これ以上探索しても結果は改善しないため、即座に return します（枝刈り）
• isFull := true、pos := -1、minH := inf で初期化します
• i を 1 から n までループします
  • h[i] < m なら、まだ余白のある列が存在するので isFull := false とします
  • h[i] < minH なら、minH := h[i]、pos := i と更新し、最も低い列の位置を記録します
• isFull が true（すべての列が高さ m に達している）なら、res := min(res, cnt) として return します
• 盤面の状態を一意に表すキー key を計算します。key := 0、base := m + 1 とし、i を 1 から n までループしながら key += h[i] * base、base *= (m + 1) と更新していきます
• key がすでに s に登録されており、s[key] <= cnt である場合は、同じ状態をより少ない個数で探索済みのため return します
• s[key] := cnt として現在の状態とコストを記録します
• end := pos とし、「end + 1 <= n かつ h[end + 1] == h[pos] かつ (end + 1 - pos + 1 + minH) <= m」を満たす間 end を増やします。これは、同じ高さが続く列の中で正方形を置ける最大範囲を求める処理です
• j を end から pos まで減らしながらループします
  • curH := j - pos + 1（このとき置ける正方形の一辺の長さ）
  • サイズ n + 1 の配列 next を新しく作り、next[i] := h[i] としてコピーします
  • k を pos から j までループし、next[k] += curH と更新します（正方形を置いた分だけ高さが増える）
  • dfs(n, m, next, cnt + 1) を再帰的に呼び出します

メイン関数での処理

• n == m の場合、長方形そのものが正方形なので 1 を返します
• n > m の場合は swap(n, m) で入れ替えておきます
• サイズ n + 1 の配列 h を定義します
• dfs(n, m, h, 0) を呼び出します
• 最後に res を返します

以下の実装例を見ると、理解がさらに深まるでしょう。

実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map<int, int> s;
   int res = INT_MAX;
   void dfs(int n, int m, vector<int> h, int cnt){
      if (cnt >= res)
         return;
      bool isFull = true;
      int pos = -1, minH = INT_MAX;
      for (int i = 1; i <= n; i++) {
         if (h[i] < m)
            isFull = false;
         if (h[i] < minH) {
            minH = h[i];
            pos = i;
         }
      }
      if (isFull) {
         res = min(res, cnt);
         return;
      }
      long key = 0;
      long base = m + 1;
      for (int i = 1; i <= n; i++) {
         key += h[i] * base;
         base *= m + 1;
      }
      if (s.find(key) != s.end() && s[key] <= cnt)
         return;
      s[key] = cnt;
      int end = pos;
      while (end + 1 <= n && h[end + 1] == h[pos] && (end + 1 - pos + 1 + minH) <= m)
      end++;
      for (int j = end; j >= pos; j--) {
         int curH = j - pos + 1;
         vector<int> next(n + 1);
         for (int i = 1; i <= n; i++)
            next[i] = h[i];
         for (int k = pos; k <= j; k++) {
            next[k] += curH;
         }
         dfs(n, m, next, cnt + 1);
      }
   }
   int tilingRectangle(int n, int m){
      if (n == m)
         return 1;
      if (n > m)
         swap(n, m);
      vector<int> h(n + 1);
      dfs(n, m, h, 0);
      return res;
   }
};
main(){
   Solution ob;
   cout << (ob.tilingRectangle(2, 3));
}

入力

2,3

出力

3