home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

การปูกระเบื้องโดมิโนและโทรมิโนใน C++

สมมุติว่าเรามีรูปร่างสองแบบ คือ Domino และ Tromino สามารถหมุนได้ดังนี้ -

การปูกระเบื้องโดมิโนและโทรมิโนใน C++

ในการปูกระเบื้อง ทุกตารางต้องปูด้วยกระเบื้อง การเรียงต่อกันสองแบบในที่นี้จะต่างกันก็ต่อเมื่อมีเซลล์ที่อยู่ติดกัน 4 ทิศทาง 2 เซลล์บนกระดาน โดยที่การเรียงต่อกันอย่างใดอย่างหนึ่งมีสี่เหลี่ยมจัตุรัสทั้งสองอันถูกไทล์ครอบครอง

ให้ N แล้วเราต้องค้นหาว่าเราจะเรียงบอร์ด 2xN ได้กี่วิธี? ดังนั้นหากอินพุตเป็น 3 เอาต์พุตจะเป็น 5 ดังนั้นการจัดเรียงอาจเป็น [XYZ XXZ XYY XXY XYY] และ [XYZ YYZ XZZ XYY XXY] ในที่นี้จะมีการใช้ตัวอักษรต่างกันสำหรับไทล์ต่างๆ

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

  • สร้างอาร์เรย์ชื่อ dp ขนาด N + 5 ตั้งค่า dp[1] :=1 dp[2] :=2 และ dp[3] :=5

  • สำหรับฉันอยู่ในช่วง 4 ถึง N

    • dp[i] :=2*dp[i – 1] + dp[i – 3]

  • กลับ dp[N]

ตัวอย่าง(C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b){
   return ((a % MOD) + (b % MOD)) % MOD;
}
class Solution {
   public:
   int numTilings(int N) {
      vector <int> dp(N + 5);
      dp[1] = 1;
      dp[2] = 2;
      dp[3] = 5;
      for(int i = 4; i <= N; i++){
         dp[i] = add(2 * dp[i - 1], dp[i - 3]);
      }
      return dp[N];
   }
};
main(){
   Solution ob;
   cout << (ob.numTilings(3));
}

อินพุต

3

ผลลัพธ์

5