Xếp hình chữ nhật với ít ô vuông nhất trong C ++

Giả sử chúng ta có một hình chữ nhật kích thước n x m. Chúng ta phải tìm số lượng tối thiểu các đối tượng hình vuông cạnh các số nguyên có thể xếp các hình chữ nhật.

Vì vậy, nếu đầu vào là n =2 và m =3,

thì đầu ra sẽ là 3, vì chúng ta cần ba khối.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một bản đồ m

• res:=inf

• Xác định một hàm dfs (), hàm này sẽ lấy n, m, một mảng h, cnt,

• nếu cnt> =res, thì -

  • trở lại

• isFull:=true

• pos:=-1, minH:=inf

• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -

  • nếu h [i]

    • isFull:=false

  • nếu h [i]

    • minH:=h [i]

    • pos:=i

• nếu isFull khác 0, thì -

  • res:=tối thiểu res và cnt

  • trở lại

• khóa:=0

• cơ sở:=m + 1

• để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -

  • key:=key + h [i] * base

  • cơ sở:=cơ sở * (m + 1)

• nếu khóa bằng s và s [key] <=cnt, thì -

  • trở lại

• s [key]:=cnt

• end:=pos

• while (end + 1 <=n và h [end + 1] giống với h [pos] và (end + 1 - pos + 1 + minH)

• <=m), làm -

  • (tăng cuối cùng lên 1)

• để khởi tạo j:=end, khi j> =pos, update (giảm j đi 1), do -

  • curH:=j - pos + 1

  • Xác định một mảng tiếp theo có kích thước n + 1

  • để khởi tạo i:=1, khi i <=n, cập nhật (tăng i lên 1), thực hiện -

    • tiếp theo [i]:=h [i]

  • để khởi tạo k:=pos, khi k <=j, cập nhật (tăng k lên 1), thực hiện -

    • tiếp theo [k]:=tiếp theo [k] + curH

  • dfs (n, m, tiếp theo, cnt + 1)

• Từ phương thức chính, thực hiện như sau -

• nếu n giống với m thì -

  • trả lại 1

• nếu n> m thì

  • hoán đổi (n, m)

• Xác định một mảng h có kích thước n + 1

• dfs (n, m, h, 0)

• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

2,3

Đầu ra

3