数独是一种流行的单人游戏。
目标是用数字填充9x9矩阵,使每列,每行和所有9个非重叠的3x3子矩阵包含从1到9的所有数字。
每个9x9矩阵在游戏开始时都会有部分数字已经给出,通常有一个独特的解决方案。
给定完成的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
提前判断不合法的值
set记录每一行每一列每个小块出现的数的个数
注意每次清空set
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=520;
set<ll>hang[N],lie[N],kuai[N];
int main()
{
ll t;
cin>>t;
for(ll op=1;op<=t;op++)
{
ll n;cin>>n;
ll nn=n;n*=n;
ll flag=0;
for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)
{
ll x;cin>>x;
if(x>n)flag=1; //判断不合法的值;
hang[i].insert(x),lie[j].insert(x),kuai[((i+nn-1)/nn-1)*nn+(j+nn-1)/nn].insert(x);
}
for(ll i=1;i<=n;i++)
{
if(hang[i].size()!=n||lie[i].size()!=n||kuai[i].size()!=n)flag=1;
hang[i].clear(); //清空set;
lie[i].clear();
kuai[i].clear();
}
if(!flag)cout<<"Case #"<<op<<": Yes"<<endl;
else cout<<"Case #"<<op<<": No"<<endl;
}
}