ボードのあるグリッドに色を付ける方法の数を調べるC++プログラム

2行n列のグリッドが与えられたとします。グリッドは、1つのボードが別のボードを乗り越えないように、n個のボードでカバーする必要があります。ここで、ボードは赤、青、緑の間の任意の1色で着色する必要があります。隣接する2枚のボードを同じ色で着色することはできません。必要がなければ、すべての色を使用する必要はありません。グリッドの構成は配列「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