AcWing 703. 数独检查(思路清晰,暴力模拟)
原题链接
简单
作者:
Diviner
,
2021-02-04 10:59:05
,
所有人可见
,
阅读 353
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 40;
int a[N][N],s[N];
int n,m;
bool check_row()
{
for(int i = 1; i <= m; i ++)
{
memset(s, 0, sizeof s);
for(int j = 1; j <= m; j ++)
{
s[a[i][j]] ++;
if(s[a[i][j]] > 1) return false;
}
}
}
bool check_col()
{
for(int i = 1; i <= m; i ++)
{
memset(s, 0, sizeof s);
for(int j = 1; j <= m; j ++)
{
s[a[j][i]] ++;
if(s[a[j][i]] > 1) return false;
}
}
return true;
}
bool check()
{
for(int l = 0; l < m; l ++)
{
memset(s, 0, sizeof s);
for(int i = 1 + l/n*n; i <= l/n*n + n; i ++)
{
for(int j = 1 + n*(l%n); j <= n*(l%n) + n; j ++)
{
s[a[i][j]] ++;
if(s[a[i][j]] > 1) return false;
}
}
}
return true;
}
int main()
{
int t;
cin >> t;
for(int k = 1; k <= t; k ++)
{
int flag = 1;
cin >> n;
m = n * n;
for(int i = 1; i <= m; i ++)
{
for(int j = 1; j <= m; j ++)
{
cin >> a[i][j];
if(a[i][j] > m || a[i][j] < 1) flag = 0;
}
}
if(flag && check_row() && check_col() && check()) cout << "Case #" << k << ": Yes" << endl;
else cout << "Case #" << k << ": No" << endl;
}
return 0;
}