题意:n * m的方格,有的格子是数字,是数字的格子代表了相邻(包括自己)的9个格子内颜色值为1的格子有这么多个。给出这个方格,求满足条件的颜色方格,保证答案唯一。 n <= 10, m <= 10。
思路:想不出好办法,直接暴力+剪枝。 暴力好说,01dfs即可,关键是如何剪枝。剪枝肯定是已经不会再变动颜色的格子,都是满足条件的,才能继续dfs。假设当前遍历x和y,如果xy都不是第一行(列),那么左上角可以判定是否符合条件。如果x到了n+1行,那么要特判第n行,因为在第n行的时候,只判了n - 1行。如果y到了m列,要特判x - 1, m列。
void solve(){
int n, m;
cin >> n >> m;
vector<string> grid(n);
for (auto& x : grid){
cin >> x;
}
vector<vector<int>> colors(n, vector<int>(m));
auto check = [&](int x, int y)->bool{
if (grid[x][y] == '_'){
return true;
}
int cnt = 0;
for (int i = -1; i <= 1; ++i){
for (int j = -1; j <= 1; ++j){
int pi = x + i;
int pj = y + j;
if (min(pi, pj) >= 0 && pi < n && pj < m){
cnt += colors[pi][pj];
}
}
}
return static_cast<bool>(cnt == (grid[x][y] - '0'));
};
function<bool(int, int)> dfs = [&](int x, int y) -> bool{
if (x == n){
for (int i = 0; i < m; ++i){
if (check(n - 1, i) == false){
return false;
}
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; ++j){
cout << colors[i][j];
}
cout << "\n";
}
return true;
}
if (y < m - 1){
colors[x][y] = 0;
if ((x == 0 || y == 0 || check(x - 1, y - 1)) && dfs(x, y + 1)){
return true;
}
colors[x][y] = 1;
if ((x == 0 || y == 0 || check(x - 1, y - 1)) && dfs(x, y + 1)){
return true;
}
}
else{
colors[x][y] = 0;
if ((x == 0 || (check(x - 1, y - 1) && check(x - 1, y))) && dfs(x + 1, 0)){
return true;
}
colors[x][y] = 1;
if ((x == 0 || (check(x - 1, y - 1) && check(x - 1, y))) && dfs(x + 1, 0)){
return true;
}
}
return false;
};
dfs(0, 0);
}
总结:经典暴力+剪枝。洛谷没ac,蓝桥ac了,估计有点小bug,有缘再调。
标签:剪枝,洛谷,格子,int,P9237,蓝桥,grid,return From: https://www.cnblogs.com/yxcblogs/p/18097154