PTA L1-104 九宫格(C++ 含代码解释)

九宫格是一款数字游戏，传说起源于河图洛书，现代数学中称之为三阶幻方。游戏规则是：将一个 9×9 的正方形区域划分为 9 个 3×3 的正方形宫位，要求 1 到 9 这九个数字中的每个数字在每一行、每一列、每个宫位中都只能出现一次。
本题并不要求你写程序解决这个问题，只是对每个填好数字的九宫格，判断其是否满足游戏规则的要求。

输入格式：

输入首先在第一行给出一个正整数 n（≤10），随后给出 n 个填好数字的九宫格。每个九宫格分 9 行给出，每行给出 9 个数字，其间以空格分隔。

输出格式：

对每个给定的九宫格，判断其中的数字是否满足游戏规则的要求。满足则在一行中输出 1，否则输出 0。

输入样例：

3
5 1 9 2 8 3 4 6 7
7 2 8 9 6 4 3 5 1
3 4 6 5 7 1 9 2 8
8 9 2 1 4 5 7 3 6
4 7 3 6 2 8 1 9 5
6 5 1 7 3 9 2 8 4
9 3 4 8 1 6 5 7 2
1 6 7 3 5 2 8 4 9
2 8 5 4 9 7 6 1 3
8 2 5 4 9 7 1 3 6
7 9 6 5 1 3 8 2 4
3 4 1 6 8 2 7 9 5
6 8 4 2 7 1 3 5 9
9 1 2 8 3 5 6 4 7
5 3 7 9 6 4 2 1 8
2 7 9 1 5 8 4 6 3
4 5 8 3 2 6 9 7 1
1 6 3 7 4 9 5 8 3
81 2 5 4 9 7 1 3 6
7 9 6 5 1 3 8 2 4
3 4 1 6 8 2 7 9 5
6 8 4 2 7 1 3 5 9
9 1 2 8 3 5 6 4 7
5 3 7 9 6 4 2 1 8
2 7 9 1 5 8 4 6 3
4 5 8 3 2 6 9 7 1
1 6 3 7 4 9 5 8 2

输出样例：

1
0
0

思路：

这是一道看着不难，实际很烦的题目。比较恶心的点在于如何判断“1-9这九个数字在每个宫位都只出现了一次”，这里我直接使用最直观的方法。因为题目已经默认九宫格有九个宫位，所以我们可以直接确定每个宫位正中心的坐标，如果数组下标是从0开始的话，其横坐标就是1，4，7，纵坐标也是1，4，7。根据排列组合的知识，一共有9种坐标组合，我这里开了两层for循环。每层for循环直接枚举该点上下左右九个点(含自己)的坐标。同时，我使用了set容器来存取数字，只有当s.size()==9,才说明满足条件。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int a[N][N];
int h[3]={1,4,7}; //行坐标
int l[3]={1,4,7}; //列坐标
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
while(n–)
{
int f=1; //标记
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
cin>>a[i][j];
if(a[i][j]<1||a[i][j]>9) f=0; //输入的时候直接判断元素是否越界
}
}
if(!f) //如果越界，直接continue
{
cout<<'0'<<'\\n';
continue;
}
for(int i=0;i<9;i++) //判断每行是否都有1-9这9个数字
{
set<int>s; //使用set容器来存储数据
for(int j=0;j<9;j++) s.insert(a[i][j]);
if(s.size()!=9)
{
f=0;
break;
}
}
for(int j=0;j<9;j++) //判断每列是否都有1-9这9个数字
{
set<int>s;
for(int i=0;i<9;i++) s.insert(a[i][j]);
if(s.size()!=9)
{
f=0;
break;
}
}
if(!f)
{
cout<<0<<'\\n';
continue;
}
for(int i=0;i<3;i++) //判断每个宫位是否都有1-9这9个数字
{
set<int>s;
int hh=h[i]; //先固定行坐标
for(int j=0;j<3;j++)
{
int ll=l[j];
s.insert(a[hh][ll]); //直接枚举宫位中心向四周的9个点坐标
s.insert(a[hh][ll-1]);
s.insert(a[hh][ll+1]);
s.insert(a[hh-1][ll-1]);
s.insert(a[hh-1][ll]);
s.insert(a[hh-1][ll+1]);
s.insert(a[hh+1][ll-1]);
s.insert(a[hh+1][ll]);
s.insert(a[hh+1][ll+1]);
if(s.size()!=9) //如果set中没有存满9个数,说明不满足条件
{
f=0;
break;
}
}
if(!f) break;
}
if(!f) cout<<0<<'\\n';
if(f) cout<<1<<'\\n';
}
}

评测详情：