C ++程序找出可以为带有板的网格着色的方式数量
假设，我们有一个 2 行 n 列的网格。网格必须被 n 块板覆盖，而一块板不能超过另一块板。现在，棋盘必须用红色、蓝色和绿色之间的任何一种颜色着色。相邻的两块板不能用相同的颜色着色，如果没有必要，也不必使用所有颜色。网格的配置在数组“grid”中给出，其中网格中的特定板使用相同的英文字母表示，不同的板使用不同的英文字母表示。我们必须找出可以为木板着色的方法的数量。
所以，如果输入像 n = 4, grid = {"abbd", "accd"}，那么输出将是 6。
有 6 种不同的方法可以为满足给定标准的板着色。
脚步
为了解决这个问题，我们将遵循以下步骤 -
MODVAL := 10^9 + 7Define 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
以上是 C ++程序找出可以为带有板的网格着色的方式数量 的全部内容， 来源链接： utcz.com/z/297225.html
