โปรแกรม C++ เพื่อค้นหาจำนวนวิธีที่สามารถทำสีตารางกับกระดานได้

สมมติว่าเราได้รับตารางที่มี 2 แถวและ n คอลัมน์ ตารางจะต้องถูกครอบคลุมโดยกระดาน n กระดานโดยที่กระดานหนึ่งไม่สามารถผ่านอีกกระดานหนึ่งได้ ตอนนี้ กระดานจะต้องมีสีใดสีหนึ่งระหว่างสีแดง สีน้ำเงิน และสีเขียว กระดานสองแผ่นที่อยู่ติดกันไม่สามารถระบายสีด้วยสีเดียวกันได้ และถ้าไม่จำเป็น ก็ไม่จำเป็นต้องใช้สีทั้งหมด การกำหนดค่าของกริดมีอยู่ในอาร์เรย์ 'กริด' โดยที่บอร์ดในตารางจะแสดงโดยใช้ตัวอักษรภาษาอังกฤษตัวเดียวกัน และกระดานต่างๆ จะแสดงโดยใช้ตัวอักษรภาษาอังกฤษต่างกัน เราต้องหาจำนวนวิธีที่จะลงสีกระดาน

ดังนั้น หากอินพุตเป็น n =4, grid ={"abbd", "accd"} เอาต์พุตจะเป็น 6

มี 6 วิธีในการระบายสีกระดานตามเกณฑ์ที่กำหนด

ขั้นตอน

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

MODVAL := 10^9 + 7
Define an array s
for initialize i := 0, when i < n, do:
   if grid[0, i] is same as grid[1, i], then:
      insert 1 at the end of s
      (increase i by 1)
   Otherwise,
      insert 2 at the end of s
      i := i + 2
Define an array tvec
if s[0] is same as 1, then:
   tvec[0] := 3
Otherwise,
   tvec[0] := 6
for initialize i := 1, when i < size of s, update (increase i by 1), do:
   if s[i - 1] is same as 2 and s[i] is same as 2, then:
      tvec[i] := tvec[i - 1] * 3 mod MODVAL
   if s[i - 1] is same as 2 and s[i] is same as 1, then:
      tvec[i] := tvec[i - 1]
   if s[i - 1] is same as 1 and s[i] is same as 2, then:
      tvec[i] := tvec[i - 1] * 2 mod MODVAL
   if s[i - 1] is same as 1 and s[i] is same as 1, then:
      tvec[i] := tvec[i - 1] * 2 mod MODVAL
return tvec[size of s - 1]

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;

int solve(int n, vector<string> grid){
   int MODVAL = 1e9 + 7;
   vector<int> s;
   for (int i = 0; i < n;) {
      if (grid[0][i] == grid[1][i]) {
         s.push_back(1);
         i++;
      } else {
         s.push_back(2);
         i += 2;
      }
   }
   vector<int> tvec(s.size());
   if (s[0] == 1)
      tvec[0] = 3;
   else
      tvec[0] = 6;
   for (int i = 1; i < (int)s.size(); i++) {
      if (s[i - 1] == 2 && s[i] == 2)
         tvec[i] = tvec[i - 1] * 3 % MODVAL;
      if (s[i - 1] == 2 && s[i] == 1)
         tvec[i] = tvec[i - 1];
      if (s[i - 1] == 1 && s[i] == 2)
         tvec[i] = tvec[i - 1] * 2 % MODVAL;
      if (s[i - 1] == 1 && s[i] == 1)
         tvec[i] = tvec[i - 1] * 2 % MODVAL;
   }
   return tvec[s.size() - 1];
}
int main() {
   int n = 4;
   vector <string> grid = {"abbd", "accd"};
   cout<< solve(n, grid);
   return 0;
}

อินพุต

4, {"abbd", "accd"}

ผลลัพธ์

6