การปูกระเบื้องสี่เหลี่ยมผืนผ้าด้วยกำลังสองน้อยที่สุดใน C++

สมมติว่าเรามีสี่เหลี่ยมจัตุรัสขนาด n x m เราต้องหาจำนวนขั้นต่ำของวัตถุสี่เหลี่ยมจัตุรัสด้านจำนวนเต็มที่สามารถเรียงต่อกันสี่เหลี่ยมได้

ดังนั้น หากอินพุตเป็น n =2 และ m =3

จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากเราต้องการสามช่วงตึก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งแผนที่ m

• res :=inf

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้เวลา n, m, อาร์เรย์ h, cnt,

• ถ้า cnt>=res แล้ว −

  • กลับ

• isFull :=จริง

• pos :=-1, minH :=inf

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • ถ้า h[i]

    • isFull :=เท็จ

  • ถ้า h[i]

    • minH :=h[i]

    • pos :=ฉัน

• ถ้า isFull ไม่ใช่ศูนย์ ดังนั้น −

  • res :=ขั้นต่ำของ res และ cnt

  • กลับ

• คีย์ :=0

• ฐาน :=m + 1

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • คีย์ :=คีย์ + h[i] * ฐาน

  • ฐาน :=ฐาน * (m + 1)

• ถ้าคีย์อยู่ใน s และ s[key] <=cnt แล้ว −

  • กลับ

• s[คีย์] :=cnt

• จบ :=pos

• ในขณะที่ (end + 1 <=n และ h[end + 1] เหมือนกับ h[pos] และ (end + 1 - pos + 1 + minH)

• <=m) ทำ −

  • (เพิ่มขึ้นท้าย 1)

• สำหรับการเริ่มต้น j :=end เมื่อ j>=pos อัปเดต (ลด j โดย 1) ทำ -

  • curH :=j - pos + 1

  • กำหนดอาร์เรย์ถัดไปของขนาด n + 1

  • สำหรับการเริ่มต้น i :=1 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • ต่อไป[i] :=h[i]

  • สำหรับการเริ่มต้น k :=pos เมื่อ k <=j อัปเดต (เพิ่ม k ขึ้น 1) ทำ -

    • next[k] :=next[k] + curH

  • dfs(n, m, ถัดไป, cnt + 1)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ถ้า n เท่ากับ m แล้ว −

  • กลับ 1

• ถ้า n> m แล้ว

  • สลับ(n, m)

• กำหนดอาร์เรย์ h ขนาด n + 1

• 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