大冶网站建设网站建设目录规范

题目链接：https://www.lanqiao.cn/problems/3508/learning/

个人评价：难度 3 星（满星：5）
前置知识：深度优先搜索

整体思路

深搜，在搜索过程中进行剪枝，剪枝有以下限制条件：

1. 所有已填入的 1 对周围 9 个方格数字的影响，不能超过原来棋盘上的数字；
2. 当确定了 $(x,y)$ 位置的像素颜色时，$(x-1,y-1)$ 位置的数字也确定下来了，这个由填入像素颜色确定的数字必须与棋盘上的数字相同，由此可以确定所有 $x\in [1,n),y\in [1,m)$ 位置的数字；
3. 当确定了第 $m$ 列方格的像素颜色时，第 $x-1$ 行的数字也随之确定，这个数字也必须与棋盘上的数字相同，由此可以确定所有 $x\in [1,n),y=m$ 位置的数字；
4. 当确定了第 $n$ 行方格的像素颜色时，第 $y-1$ 列的数字也随之确定，同上可确定所有 $x=n,y\in [1,m)$ 位置的数字；
5. 最后一个位置 $(n,m)$ 的像素颜色确定时，最后一个数字也随之确定，这个数字也必须与棋盘上的数字相同。

过题代码

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn = 100;
int n, m, nm;
bool flag;
int num[maxn][maxn], sum[maxn][maxn];
char str[maxn][maxn], ans[maxn][maxn];
const int dir[9][2] = {{-1, -1}, {-1, 0}, {-1, 1},{0, -1}, {0, 0}, {0, 1},{1, -1}, {1, 0}, {1, 1}
};bool in(int x, int y) {return x >= 0 && x < n && y >= 0 && y < m;
}bool check(int x, int y, int d) {for (int i = 0; i < 9; ++i) {int xx = x + dir[i][0];int yy = y + dir[i][1];if (in(xx, yy) && sum[xx][yy] + d > num[xx][yy]) {return false;}}if (in(x - 1, y - 1) && num[x - 1][y - 1] != 10 && sum[x - 1][y - 1] + d != num[x - 1][y - 1]) {return false;}if (y == m - 1 && in(x - 1, y) && num[x - 1][y] != 10 && sum[x - 1][y] + d != num[x - 1][y]) {return false;}if (x == n - 1 && in(x, y - 1) && num[x][y - 1] != 10 && sum[x][y - 1] + d != num[x][y - 1]) {return false;}if (x == n - 1 && y == m - 1 && num[x][y] != 10 && sum[x][y] + d != num[x][y]) {return false;}return true;
}void add(int x, int y, int d) {for (int i = 0; i < 9; ++i) {int xx = x + dir[i][0];int yy = y + dir[i][1];if (in(xx, yy)) {sum[xx][yy] += d;}}
}void dfs(int depth) {if (depth == nm) {flag = true;for (int i = 0; i < n; ++i) {cout << ans[i] << endl;}return ;}int x = depth / m;int y = depth % m;if (check(x, y, 1)) {add(x, y, 1);ans[x][y] = '1';dfs(depth + 1);if (flag) {return ;}add(x, y, -1);ans[x][y] = '0';}if (check(x, y, 0)) {dfs(depth + 1);}
}int main() {
#ifdef ExRocfreopen("test.txt", "r", stdin);
#endif // ExRocios::sync_with_stdio(false);cin >> n >> m;nm = n * m;for (int i = 0; i < n; ++i) {cin >> str[i];for (int j = 0; j < m; ++j) {if (str[i][j] == '_') {num[i][j] = 10;} else {num[i][j] = str[i][j] - '0';}ans[i][j] = '0';}}dfs(0);return 0;
}