Online Judge——1005. 数独(c++)

题目描述

数独游戏，具体规则如下：

每一行都用到1,2,3,4,5,6,7,8,9, 位置不限，

每一列都用到1,2,3,4,5,6,7,8,9, 位置不限，

每3*3的格子（共9个这样的格子）都用到1,2,3,4,5,6,7,8,9, 位置不限，

游戏过程就是用1,2,3,4,5,6,7,8,9填充空白，并满足每行，每列，每个九宫格都用到1,2,3,4,5,6,7,8,9，

如下是个正确的sudoku:

输入格式

输入n个数独，你来验证它是否违反规则。

第一行为数独个数，第二行开始为第一个数独，之后第二个，至第n个。

注意：每个数独间有个回车隔开。

输出格式

若正确则输出"Right",否则输出"Wrong", 输出一个换一行。

说明

1<=n<=20(输入的数独个数）

不论输入的数独是否正确，数据保证每个数都在1-9间。

Sample Input

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

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

Sample Output

Right
Wrong

代码

#include <iostream>

using namespace std;

int a[9][9] = {0};
int function();
int main() {
	int num;
	cin >> num;

	for(int i = 0; i < num; i++) {
		// 输入数独
		for(int x = 0; x < 9; x++) {
			for(int y = 0; y < 9; y++) {
				cin >> a[x][y];
			}
		}

		int result = function();
		if(result == 1) cout << "Right" << endl;
		else cout << "Wrong" << endl;
	}
	return 0;
}

int function(){
	int r1[9] = {0};
	int r2[9] = {0};
	int r3[9] = {0};

	// 判断某一行/列是否为1-9
	for(int x = 0; x < 9; x++) {
		for(int y = 0; y < 9; y++) {
			// 遍历数独一行中的9个数，将其对应数作为记录数组（r1）的下标进行统计
			// 一旦统计的数量超过1，即数独违反规则
			r1[a[x][y] - 1]++;
			if(r1[a[x][y] - 1] > 1) return 0;
			// 遍历数独一列中的9个数，将其对应数作为记录数组（r2）的下标进行统计
			r2[a[y][x] - 1]++;
			if(r2[a[y][x] - 1] > 1) return 0;
		}
		// 归零
		for(int y = 0; y < 9; y++) {
			r1[y] = 0;
			r2[y] = 0;
		}
	}

	// 判断9个3*3矩阵内是否为1-9
	for(int x = 0; x < 3; x++){
		for(int y = 0; y < 3; y++){
			// 一个3*3矩阵
			for(int xx = x * 3; xx < x * 3 + 3; xx++){
				for(int yy = y * 3; yy < y * 3 + 3; yy++){
					r3[a[xx][yy] - 1]++;
					if(r3[a[xx][yy] - 1] > 1) return 0;
				}
			}
			// 归零
			for(int k = 0; k < 9; k++) {
				r3[k] = 0;
			}
		}
	}
	return 1;
}

思路

对数独的每一行（列、3*3矩阵）进行判断，利用记录数组r[]记录出现1-9数字的次数，一旦某个数出现超过一次数独非法。