上海计算机学会2024年9月月赛C++丙组T1数独验证
发布时间
阅读量：
阅读量
数独验证
内存限制: 256 Mb时间限制: 1000 ms
题目描述
九宫格数字谜题是一种考验逻辑思维能力的游戏形式。对于由9 \times 9个数字组成的矩阵，请判断其排列模式是否满足标准九宫格规则。
一个合法有效的数独矩阵必须满足以下条件：在其每一行、每一列以及每一个九宫格内都包含从1到9的所有数字而不重复。其中九宫格被定义为由前三行至后三行为一组纵向区域...由前三列为至中列为中间区域...由中列为至后三列为第三组纵向区域...同时在横向方面也分为前三列至中列为第一组横向区域...中列为至后三列为第二组横向区域...同样分为三个部分组成九宫格结构
输入格式
- 九行整数：每行九个数字表示一个矩阵。
输出格式
- 若满足数独条件，输出
Valid，否则输出Invalid
数据范围
- 保证输入的每个数字均为 1 到 9 的整数。
样例数据
输入:
8 4 5 9 3 1 6 2 7
9 1 6 5 2 7 8 3 4
7 3 2 6 4 8 9 5 1
5 7 8 4 9 3 2 1 6
2 6 1 8 7 5 3 4 9
4 9 3 2 1 6 5 7 8
6 8 7 1 5 2 4 9 3
3 5 9 7 6 4 1 8 2
1 2 4 3 8 9 7 6 5输出:
Valid
输入:
1 1 1 2 2 2 3 3 3
4 4 4 5 5 5 6 6 6
7 7 7 8 8 8 9 9 9
1 1 1 2 2 2 3 3 3
4 4 4 5 5 5 6 6 6
7 7 7 8 8 8 9 9 9
1 1 1 2 2 2 3 3 3
4 4 4 5 5 5 6 6 6
7 7 7 8 8 8 9 9 9
输出:
Invalid
解析：详见代码：
#include<bits/stdc++.h>
using namespace std;
int n = 9;
int a[10][10];
bool b[10];
int main() {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for(int i = 1; i <= n; i++) { //枚举行
memset(b, 0, sizeof(b));
for(int j = 1; j <= n; j++) { //标记出现的数字
b[a[i][j]] = 1;
}
for(int j = 1; j <= n; j++) { //验证
if(b[j] != 1) { //有一个不是1
cout << "Invalid"; //验证不通过
return 0;
}
}
}
for(int i = 1; i <= n; i++) { //枚举列
memset(b, 0, sizeof(b));
for(int j = 1; j <= n; j++) {
b[a[j][i]] = 1;
}
for(int j = 1; j <= n; j++) {
if(b[j] != 1) {
cout << "Invalid";
return 0;
}
}
}
for(int k = 1; k <= n; k += 3) { //枚举3行3列共九个宫
for(int l = 1; l <= n; l += 3) {
memset(b, 0, sizeof(b));
for(int i = k; i < k + 3; i++) {
for(int j = l; j < l + 3; j++) {
b[a[j][i]] = 1;
}
}
for(int j = 1; j <= n; j++) {
if(b[j] != 1) {
cout << "Invalid";
return 0;
}
}
}
}
cout << "Valid";
return 0 ;
}
cpp
全部评论 (0)
还没有任何评论哟~