C++で最も少ない正方形で長方形をタイリングする

サイズがnxmの長方形があるとします。長方形を並べて表示できる整数辺の正方形オブジェクトの最小数を見つける必要があります。

したがって、入力がn=2およびm=3のような場合、

3つのブロックが必要なため、出力は3になります。

これを解決するには、次の手順に従います-

• 1つのマップを定義するm

• res：=inf

• 関数dfs（）を定義します。これには、n、m、配列h、cnt、

  が必要です。

• cnt> =resの場合、-

  • 戻る

• isFull：=true

• pos：=-1、minH：=inf

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

  • h [i]

    • isFull：=false

  • h [i]

    • minH：=h [i]

    • pos：=i

• isFullがゼロ以外の場合、-

  • res：=resとcntの最小値

  • 戻る

• キー：=0

• ベース：=m + 1

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

  • キー：=キー+ h[i]*ベース

  • ベース：=ベース*（m + 1）

• キーがsおよびs[key]<=cntにある場合、-

  • 戻る

• s [key]：=cnt

• 終了：=pos

• while（end + 1 <=n and h [end + 1] is as as h [pos] and（end + 1 --pos + 1 + minH）

• <=m）、実行-

  • （終了を1増やします）

• 初期化j：=endの場合、j> =posの場合、更新（jを1つ減らす）、do −

  • curH：=j --pos + 1

  • サイズn+1の次の配列を定義します

  • 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

    • next [i]：=h [i]

  • 初期化k：=posの場合、k <=jの場合、更新（kを1増やします）、実行-

    • next [k]：=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）

• 解像度を返す

理解を深めるために、次の実装を見てみましょう-

例

#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