보드가 있는 그리드에 색상을 지정할 수 있는 방법의 수를 알아내는 C++ 프로그램

2개의 행과 n개의 열이 있는 그리드가 있다고 가정합니다. 그리드는 한 보드가 다른 보드를 덮지 않고 n 보드로 덮여 있어야 합니다. 이제 보드는 빨강, 파랑 및 녹색 중 하나의 색상으로 색칠해야 합니다. 서로 인접한 두 개의 판은 같은 색으로 채색할 수 없으며, 필요하지 않은 경우 모든 색을 사용할 필요는 없습니다. 그리드의 구성은 'grid' 배열로 주어지며, 그리드의 특정 보드는 동일한 영문자를 사용하여 표시되고 다른 보드는 다른 영문자를 사용하여 표시됩니다. 보드를 색칠할 수 있는 방법의 수를 찾아야 합니다.

따라서 입력이 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