AcWing 703. 数独检查
原题链接
简单
作者:
wyf
,
2021-02-01 21:32:14
,
所有人可见
,
阅读 700
简单的模拟题:读取每个图,判断每行,每列,每个nn的小方格是否nn个数字都出现,同时还要判断数字是否合法,数字必须在1~n*n之间,若超出也是错误,若最后无误则返回true,但凡一个环节出现错误,返回false
#include<iostream>
#include<cstring>
using namespace std;
int t,n;
const int N=100;
int g[N][N];
bool st[N];
bool check(){
for(int i=0;i<n*n;i++){//判断每行是否合法
memset(st,0,sizeof st);
for(int j=0;j<n*n;j++){
if(g[i][j]>n*n||g[i][j]<1)return false;
if(st[g[i][j]])return false;
st[g[i][j]]=true;
}
}
for(int i=0;i<n*n;i++){//判断每列是否合法
memset(st,0,sizeof st);
for(int j=0;j<n*n;j++){
if(g[j][i]>n*n||g[j][i]<1)return false;
if(st[g[j][i]])return false;
st[g[j][i]]=true;
}
}
for(int x=0;x<n*n;x+=n){//判断每个n*n矩阵是否合法
for(int y=0;y<n*n;y+=n){
memset(st,0,sizeof st);
for(int dx=0;dx<n;dx++){
for(int dy=0;dy<n;dy++){
int t=g[x+dx][y+dy];
if(t<1||t>n*n)return false;
if(st[t]) return false;
st[t] = true;
}
}
}
}
return true;
}
int main(){
cin>>t;
for(int i=1;i<=t;i++){
cin>>n;
memset(g,0,sizeof g);
for(int i=0;i<n*n;i++)
for(int j=0;j<n*n;j++)
cin>>g[i][j];
if(check())cout<<"Case #"<<i<<": Yes"<<endl;
else cout<<"Case #"<<i<<": No"<<endl;
}
return 0;
}