2016-02-19

数独验证

文章目录

原文地址:https://ngunauj.github.io

今天做到了一个题目，判断数独验证。想起来以前写过的一个填数独的题目。http://poj.org/problem?id=2676
验证数独的题目：https://vijos.org/p/1335
是上面的填数独的简化。这里有一个比较好的方法。在判断3X3的小方块中是否满足要求时，我们可以把他转换成用sq[i][a]判断第i个小方块是否有a。这样能简化判断步骤。
具体见代码。

/* ***********************************************
Author:guanjun
Created Time  :2016/2/18 21:37:42
File Name :vijosp1335.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 10000+10
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
    int row[10][10],col[10][10],sq[10][10];
    int t,a;
    cin>>t;
    while(t--){
        cle(row),cle(col);cle(sq);
        for(int  i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                cin>>a;
                row[i][a]=1;
                col[j][a]=1;
                int x=(i-1)/3*3+(j-1)/3;//重点
                sq[x][a]=1;
            }
        }
        int mark=0;
        for(int i=1;i<=9;i++){
            for(int j=1;j<=9;j++){
                if(col[j][i]==0||row[i][j]==0||!sq[i-1][j]){mark=1;break;}
            }
            if(mark)break;
        }
        if(mark)puts("Wrong");
        else puts("Right");
    }
return 0;
}