Chương trình C ++ để tìm ra số cách một lưới có bảng có thể được tô màu

Giả sử, chúng ta được cung cấp một lưới có 2 hàng và n cột. Lưới phải được bao phủ bởi n bảng mà không có bảng nào vượt qua bảng khác. Bây giờ, các bảng phải được tô bằng một màu bất kỳ giữa đỏ, xanh dương và xanh lá cây. Hai bảng liền nhau không được tô cùng màu và nếu không cần thiết thì không phải dùng tất cả các màu. Cấu hình của lưới được đưa ra trong mảng 'lưới', trong đó một bảng cụ thể trong lưới được biểu diễn bằng cách sử dụng cùng một chữ cái tiếng Anh và các bảng khác nhau được biểu thị bằng các chữ cái tiếng Anh khác nhau. Chúng tôi phải tìm ra số cách có thể tô màu cho bảng.

Vì vậy, nếu đầu vào là n =4, grid ={"abbd", "accd"}, thì đầu ra sẽ là 6.

Có 6 cách khác nhau để tô màu bảng thỏa mãn tiêu chí đã cho.

Các bước

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

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]

Ví dụ

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

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

Đầu vào

4, {"abbd", "accd"}

Đầu ra

6