AcWing 703. 数独检查
原题链接
简单
作者:
我要出去乱说
,
2021-02-08 00:46:34
,
所有人可见
,
阅读 311
#include <iostream>
#include <cstring>
using namespace std;
const int N = 40;
int n, m;
int w[N][N];
bool st[N];
bool row()
{
for (int i = 0; i < m; i ++ )
{
memset(st, 0, sizeof st); //遍历每行之前初始化状态值
for (int j = 0; j < m; j ++ )
{
int t = w[i][j];
if (t > m || t < 1 || st[t]) return false; //在数据范围外或已经重复则返回false
st[t] = true; //状态更新,继续判断该行下一个数
}
}
return true;
}
bool col() //与行判断为对称关系
{
for (int i = 0; i < m; i ++ )
{
memset(st, 0, sizeof st);
for (int j = 0; j < m; j ++ )
{
int t = w[j][i];
if (t > m || t < 1 || st[t]) return false;
st[t] = true;
}
}
return true;
}
bool cell()
{
for (int x = 0; x < m; x += n) //注意此处是按小方块来遍历的
for (int y = 0; y < m; y += n)
{
memset(st, 0, sizeof st);
for (int dx = 0; dx < n; dx ++ ) //小方块要用偏移量
for (int dy = 0; dy < n; dy ++ )
{
int t = w[x + dx][y + dy];
if (t > m || t < 1 || st[t]) return false;
st[t] = true;
}
}
return true;
}
int main()
{
int T;
cin >> T;
for (int k = 1; k <= T; k ++ )
{
cin >> n;
m = n * n;
for (int i = 0; i < m; i ++ )
for (int j = 0; j < m; j ++ )
cin >> w[i][j];
if (col() && row() && cell()) //行列及子矩阵内都没有重复数字,输出Yes
printf("Case #%d: Yes\n", k);
else
printf("Case #%d: No\n", k);
}
return 0;
}