資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告