基本上都是直接暴力检查,这里行和列可以一起检查,而小方格需单独处理更好。
题目描述
给定完成的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
时间复杂度 % n^4 %
C++ 代码
include [HTML_REMOVED]
using namespace std;
const int N = 1e3;
int t,n,a[N][N],b[N],c[N],d[N];
bool check(){
for(int i = 0; i < n; i){
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(int j = 0; j < n; j){
if(b[a[i][j]] || a[i][j]>n || a[i][j]<=0||c[a[j][i]] || a[j][i]>n || a[j][i]<=0)
return false;
b[a[i][j]] = 1;
c[a[j][i]] = 1;
}
}
return true;
}
bool fge(){
n = sqrt(n);
for(int i = 0; i < n; i)
for(int j = 0; j < n; j){
memset(b,0,sizeof(b));
for(int k = 0; k < n; k)
for(int l = 0; l < n; l){
if(b[a[in+k][jn+l]] || a[in+k][jn+l]>nn || a[in+k][j*n+l]<=0)
return false;
b[a[i*n+k][j*n+l]] = 1;
}
}
return true;
}
int main(){
cin>> t;
int t1 = t;
while(t–){
cin >>n;
n*=n;
for(int i = 0; i < n; i)
for(int j = 0; j < n; j)
cin >>a[i][j];
if(check()&&fge())
cout<<"Case #"<<t1-t<<": Yes"<<endl;
else cout<<"Case #"<<t1-t<<": No"<<endl;
}
return 0;