703. 数独检查
算法
可以通过数组来存每行,每列,以及每个$n\times n$宫格里面是不是有重复的数字,这样代码能够精简很多。代价就是需要额外的空间来存储这些状态。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N=40;
int n, T, g[N][N];
bool row[N][N], col[N][N], blk[N][N];
bool valid() {
memset(row, 0, sizeof row);
memset(col, 0, sizeof col);
memset(blk, 0, sizeof blk);
for (int i=0; i<n*n; i++) for (int j=0; j<n*n; j++) {
int x=g[i][j];
if (x<1 || x>n*n || row[i][x] || col[x][j] || blk[i/n*n+j/n][x]) return false;
row[i][x]=true, col[x][j]=true, blk[i/n*n+j/n][x]=true;
}
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;
int t=0;
while (++t<=T) {
cin>>n;
for (int i=0; i<n*n; i++) for (int j=0; j<n*n; j++) cin>>g[i][j];
cout<<"Case #"<<t;
if (valid()) cout<<": Yes\n";
else cout<<": No\n";
}
return 0;
}