网站布局软件,dedecms 网站地图 模板,江苏联运建设有限公司网站,网站有哪些功能题目链接#xff1a;https://www.lanqiao.cn/problems/3508/learning/
个人评价#xff1a;难度 3 星#xff08;满星#xff1a;5#xff09; 前置知识#xff1a;深度优先搜索 整体思路
深搜#xff0c;在搜索过程中进行剪枝#xff0c;剪枝有以下限制条件#xf…题目链接https://www.lanqiao.cn/problems/3508/learning/
个人评价难度 3 星满星5 前置知识深度优先搜索 整体思路
深搜在搜索过程中进行剪枝剪枝有以下限制条件
所有已填入的 1 对周围 9 个方格数字的影响不能超过原来棋盘上的数字当确定了 ( x , y ) (x, y) (x,y) 位置的像素颜色时 ( x − 1 , y − 1 ) (x-1, y-1) (x−1,y−1) 位置的数字也确定下来了这个由填入像素颜色确定的数字必须与棋盘上的数字相同由此可以确定所有 x ∈ [ 1 , n ) , y ∈ [ 1 , m ) x \in [1, n),~y \in [1, m) x∈[1,n), y∈[1,m) 位置的数字当确定了第 m m m 列方格的像素颜色时第 x − 1 x - 1 x−1 行的数字也随之确定这个数字也必须与棋盘上的数字相同由此可以确定所有 x ∈ [ 1 , n ) , y m x \in [1,n),~y m x∈[1,n), ym 位置的数字当确定了第 n n n 行方格的像素颜色时第 y − 1 y - 1 y−1 列的数字也随之确定同上可确定所有 x n , y ∈ [ 1 , m ) x n, ~ y \in [1, m) xn, y∈[1,m) 位置的数字最后一个位置 ( n , m ) (n, m) (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;
}
