数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
更新于: 2022年3月2日
326 次浏览
广告