AcWing 703. 数独检查
原题链接
简单
作者:
123_14
,
2021-02-02 12:15:13
,
所有人可见
,
阅读 368
C 代码
//本题遇到的问题
//问题1:
//如果将nums和hash开成变长数组放入每个循环,那么每次循环都会开辟很大的空间,导致出现段错误
//解决方案是把他们开成全局变量,只开辟一次空间
//问题2:
//int数组能开多大的问题:在函数体中,int最大能开到518028。显然这对本题而言是不够的的
//解决方案是把int开成全局变量的数组,此时能开到20000*20000,足够解决本题
#include <stdio.h>
#include <stdbool.h>
static int nums[36*36+1][36*36+1];
static bool hash[36*36+1];
int main()
{
int n;
scanf("%d",&n);
for (int m=0;m<n;m++){
int N;
scanf("%d",&N);
for (int i=1;i<=N*N;i++){
for (int j=1;j<=N*N;j++){
scanf("%d",&nums[i][j]);
}
}
bool flag = true;
//判断行
for (int i=1;i<=N*N;i++){
memset(hash,false,sizeof(hash));
for (int j=1;j<=N*N;j++){
hash[nums[i][j]] = true;
}
for (int k=1;k<=N*N;k++){
if (hash[k] == false) flag = false;
}
}
//判断列
for (int j=1;j<=N*N;j++){
memset(hash,false,sizeof(hash));
for (int i=1;i<=N*N;i++){
hash[nums[i][j]] = true;
}
for (int k=1;k<=N*N;k++){
if (hash[k] == false) flag = false;
}
}
//判断方格
for (int left=1;left<=N*N-N+1;left+=N){
for (int up=1;up<=N*N-N+1;up+=N){
memset(hash,false,sizeof(hash));
for (int i=up;i<up+N;i++){
for (int j=left;j<left+N;j++){
hash[nums[i][j]] = true;
}
}
for (int k=1;k<=N*N;k++){
if (hash[k] == false) flag = false;
}
}
}
printf("Case #%d: %s\n",m+1,flag?"Yes":"No");
}
}