AcWing 703. 数独检查
原题链接
简单
作者:
Anoxia_3
,
2021-02-02 08:36:14
,
所有人可见
,
阅读 1003
#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#define INF 0x3f3f3f3f
#define fi first
#define se second
using namespace std;
typedef long long LL ;
typedef pair<int , int> PII;
const int N = 40;
int a[N][N] , n;
bool solve()
{
bool flag = true;
cin >> n;
int m = n * n;
for(int i = 0 ; i < m ; i++)
for(int j = 0 ; j < m ; j++)
{
cin >> a[i][j];
if(a[i][j] < 1 || a[i][j] > m) flag = false;
}
if(!flag)
{
return false;
}
//如果在一行或一列或一个小方块中一个数字重复出现就是false
for(int i = 0 ; i < m ; i++)
{
//判重数组
bool st1[40] = {false} , st2[40] = {false} , st3[40] = {false};
//枚举行
for(int j = 0 ; j < m ; j++)
if(st1[a[i][j]]) return false;
else st1[a[i][j]] = true;
//枚举列
for(int j = 0 ; j < m ; j++)
if(st2[a[j][i]]) return false;
else st2[a[j][i]] = true;
//枚举方块
for(int j = 0 ; j < n ; j++)//小方块内的行
for(int k = 0 ; k < n ; k++)//小方块内的列
{
int x = j + i / n * n , y = k + i % n * n;//要考虑前面的方块,加上一个偏移量
if(st3[a[x][y]]) return false;
else st3[a[x][y]] = true;
}
}
return true;
}
int main()
{
int T = 1;
cin >> T;
for(int turn = 1 ; turn <= T ; turn++)
{
printf("Case #%d: " , turn);
puts(solve() ? "Yes" : "No");
}
}
int x = j + i / m * m
请问此处为什么不是j+i/n*n呢?
是您对了😂,我重新跑了一遍,去看了题目的讨论板块,是y总的数据太弱了,现在加强了。
我就感觉不对劲,还得谢谢您给我的思路哈
if(st1[a[i][j]]) return false; 这句功能是如果重复出现就返回false,可以解释一下为什么这句有这个功能嘛,没太懂。
意思就是a[i][j]这个数字已经出现过了
$st$数组就是判重数组,一共有三个分别用来判断行、列和小方块里是否有重复数字。
拿行举例,一行中一共有$n*n$个格子,每出现一个数字,就给它的$st1[]$置为
true
,如果已经为true
,说明已经出现过了,就返回false
数独游戏的规则不就是每一行每一列每一个方块中不能出现重复数字吗😂
这样哇,懂了,感谢大佬。