1054.数独

Time Limit: 1000 MS Memory Limit: 32768 KB
Total Submission(s): 531 Accepted Submission(s): 108

Description

syc最近迷上了数独这个游戏，他在完成一个数独后总要费一些时间来检查。于是他把lg作为苦力拽来帮他检查。由于lg是搞基的，所以他就想写个程序来判断syc完成的数独是否正确。不过最近他在感情上遇到了一些问题没有功夫去写，就想请你帮他完成这个任务。
数独规则：拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。

Input

一个9*9个矩阵

每个为1到9的数字

Output

一个数字，1为构成数独，0为不构成数独

Sample Input

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

Sample Output

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[15][15];
 4 bool a1[15][15];
 5 bool a2[15][15];
 6 int i,j,k,n,tmp,tmp1;
 7 bool ans;
 8 int main()
 9 {
10     while(scanf("%d",&n)!=EOF)
11     {
12         ans=1;
13         memset(a1,0,sizeof(a1));
14         memset(a2,0,sizeof(a2));
15         for(i=1;i<=9;i++)
16         {
17             for(j=1;j<=9;j++)
18             {
19                 if(i==1&&j==1)
20                 {
21                     a[1][1]=n;
22                 }
23                 else
24                 {
25                     scanf("%d",&a[i][j]);
26                 }
27             }
28         }//存图
29         for(i=1;i<=9;i++)
30         {
31             for(j=1;j<=9;j++)
32             {
33                 a1[i][ a[i][j] ]=1;//bool a1
34             }
35         }//横着
36         for(i=1;i<=9;i++)
37         {
38             for(j=1;j<=9;j++)
39             {
40                 a1[i][ a[j][i] ]=1;//bool a1
41             }
42         }//竖着
43         tmp=1;
44         tmp1=0;
45         for(i=1;i<=3;i++)//三次循环
46         {
47             ++tmp1;
48             for(j=tmp;j<=tmp+2;j++)
49             {
50                 for(k=1;k<=3;k++)
51                 {
52                     a2[tmp1][ a[j][k] ]=1;
53 //                    cout<<"a2["<<j<<"]["<<k<<']'<<"yijingxieru"<<"a["<<tmp1<<"]["<<a[j][k]<<']'<<'
'<<endl;
54                 }
55             }//第一块
56             ++tmp1;
57             for(j=tmp;j<=tmp+2;j++)
58             {
59                 for(k=4;k<=6;k++)
60                 {
61                     a2[tmp1][ a[j][k] ]=1;
62 //                    cout<<"a2["<<j<<"]["<<k<<']'<<"yijingxieru"<<"a["<<tmp1<<"]["<<a[j][k]<<']'<<'
'<<endl;
63                 }
64             }//第二块
65             ++tmp1;
66             for(j=tmp;j<=tmp+2;j++)
67             {
68                 for(k=7;k<=9;k++)
69                 {
70                     a2[tmp1][ a[j][k] ]=1;
71 //                    cout<<"a2["<<j<<"]["<<k<<']'<<"yijingxieru"<<"a["<<tmp1<<"]["<<a[j][k]<<']'<<'
'<<endl;
72                 }
73             }//第三块
74             tmp+=3;
75         }
76         for(i=1;i<=9;i++)
77         {
78             for(j=1;j<=9;j++)
79             {
80                 if(a1[i][j]==0)
81                 {
82 //                    cout<<"NO"<<endl;
83                     ans=0;
84                     break;
85                 }
86                 if(a2[i][j]==0)
87                 {
88 //                    cout<<"a2["<<i<<"]["<<j<<']'<<endl;
89                     ans=0;
90                     break;
91                 }
92             }
93         }
94         cout<<ans<<endl;
95     }
96 }