首页 > 代码库 > POJ 3435 Sudoku Checker
POJ 3435 Sudoku Checker
Description
The puzzle game of Sudoku is played on a board of N2 × N2 cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N2.
The sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct position, fill all empty cells so that the final position is still correct.
This game is fairly popular in the Internet, and there are many sites which allow visitors to solve puzzles online. Such sites always have a subroutine to determine a correctness of a given position.
You are to write such a routin.
Input
Input file contains integer N, followed by N4 integers — sudoku position. Empty cells are denoted by zeroes.
Constraints
1 ≤ N ≤ 10.
Output
Output file must contain a single string ‘CORRECT‘ or ‘INCORRECT‘.
Sample Input
Sample input 1 2 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 1 Sample input 2 2 2 1 3 0 3 2 4 0 1 3 2 4 0 0 0 1
Sample Output
Sample output 1 CORRECT Sample output 2 INCORRECT
卧槽,数独,判断行,列和小方格里的数不重复。但只判断当前状态。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<limits.h> using namespace std; const int maxn=110; int a[maxn][maxn],n; int x[maxn][15]; int y[maxn][15]; int s[maxn][15]; int main() { while(~scanf("%d",&n)) { memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); memset(s,0,sizeof(s)); bool flag=true; for(int i=0;i<n*n;i++) { for(int j=0;j<n*n;j++) { scanf("%d",&a[i][j]); if(a[i][j]>0&&flag) { if(!x[i][a[i][j]])//判断行 x[i][a[i][j]]=1; else flag=false; if(!y[j][a[i][j]])//判断列 y[j][a[i][j]]=1; else flag=false; if(!s[i/n*n+j/n+1][a[i][j]])//判断小方格 s[i/n*n+j/n+1][a[i][j]]=1; else flag=false; } } } if(flag) printf("CORRECT\n"); else printf("INCORRECT\n"); } return 0; }