太原网站制作多少钱,哈尔滨网站建设价格低,怎么做网站写书,虚拟主机哪家好**数独是一种流行的单人游戏。 目标是用数字填充9x9矩阵#xff0c;使每列#xff0c;每行和所有9个非重叠的3x3子矩阵包含从1到9的所有数字。 每个9x9矩阵在游戏开始时都会有部分数字已经给出#xff0c;通常有一个独特的解决方案。
给定完成的N2∗N2数独矩阵#xff0c…**数独是一种流行的单人游戏。 目标是用数字填充9x9矩阵使每列每行和所有9个非重叠的3x3子矩阵包含从1到9的所有数字。 每个9x9矩阵在游戏开始时都会有部分数字已经给出通常有一个独特的解决方案。
给定完成的N2∗N2数独矩阵你的任务是确定它是否是有效的解决方案。 有效的解决方案必须满足以下条件 每行包含从1到N2的每个数字每个数字一次。 每列包含从1到N2的每个数字每个数字一次。 将N2∗N2矩阵划分为N2个非重叠N∗N子矩阵。 每个子矩阵包含从1到N2的每个数字每个数字一次。 你无需担心问题的唯一性只需检查给定矩阵是否是有效的解决方案即可。**
输入格式 第一行包含整数T表示共有T组测试数据。 每组数据第一行包含整数N。 接下来N2行每行包含N2个数字均不超过1000用来描述完整的数独矩阵。
输出格式 每组数据输出一个结果每个结果占一行。 结果表示为“Case #x: y”其中x是组别编号从1开始如果给定矩阵是有效方案则y是Yes否则y是No。
数据范围 1≤T≤100, 3≤N≤6 输入样例 3 3 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 3 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 3 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 999 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 输出样例 Case #1: Yes Case #2: No Case #3: No
代码如下
#includeiostream
#include cstring
using namespace std;
const int N 40;
int a[N][N];
bool st[N];
int n,m,cnt;
bool check_row()
{for (int i 0;im;i){memset(st,0,sizeof(st));for (int j 0;jm;j){int t a[i][j];if (t 1 || t m) return false;if (st[t]) return false;st[t] true;}}return true;
}bool check_col()
{for (int i 0;im;i){memset(st,0,sizeof(st));for (int j 0;jm;j){int t a[j][i];if (t 1 || t m) return false;if (st[t]) return false;st[t] true;}}return true;
}bool check_cell()
{for (int i 0;im;in)for(int j 0;jm;jn){memset(st,0,sizeof(st));for (int dx 0;dxn;dx)for(int dy 0;dyn;dy){int t a[idx][jdy];if (t 1 || t m) return false;if (st[t]) return false;st[t] true;}}return true;
}int main()
{cincnt;for (int i 1;icnt;i){cinn;m n*n;for (int x 0;xm;x)for (int y 0;ym;y)cina[x][y];if (check_row() check_col() check_cell()){printf(Case #%d: Yes\n,i);}else{printf(Case #%d: No\n,i);}}return 0;
}
