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, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • যদি h[i]

    • isFull :=মিথ্যা

  • যদি h[i]

    • minH :=h[i]

    • pos :=i

• যদি isFull অ-শূন্য হয়, তাহলে −

  • res :=ন্যূনতম res এবং cnt

  • ফেরত

• কী :=0

• ভিত্তি :=m + 1

• আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • key :=কী + h[i] * বেস

  • ভিত্তি :=ভিত্তি * (m + 1)

• যদি কী s এবং s[key] <=cnt-এ থাকে, তাহলে −

  • ফেরত

• s[কী] :=cnt

• শেষ :=pos

• যখন (শেষ + 1 <=n এবং h[end + 1] h[pos] এবং (end + 1 - pos + 1 + minH)

• <=মি), করো −

  • (শেষ 1 দ্বারা বৃদ্ধি করুন)

• j শুরু করার জন্য :=শেষ, যখন j>=pos, আপডেট করুন (j 1 দ্বারা কম করুন), −

  • curH :=j - pos + 1

  • n + 1

    আকারের পাশে একটি অ্যারে সংজ্ঞায়িত করুন

  • আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

    • পরবর্তী[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