ACM复习(20)8627 数独

Description
这是一个非常出名的游戏,相信大家都玩过了吧?数独需要聪明的头脑,灵敏的感觉,严密的逻辑思维,
和忽然抽风的灵感爆发。这也正是acm 这个游戏所需要的。所以集训队员们通常玩数独很牛叉~像钟教
主就能瞬秒骨灰级难度的数独题。
下面介绍摘自网上:
数独顾名思义——每个数字只能出现一次。数独是一种源自18世纪末的瑞士,后在美国发展、并
在日本得以发扬光大的数字谜题。数独盘面是个九宫,每一宫又分为九个小格(如左图)。在这八
十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9 的数字。使
1-9每个数字在每一行、每一列和每一宫中都只出现一次(如右图中已经填写完整的那样,不能重
复,独立存在)

这里写图片描述

写数独求解程序大家已经练习过很多次,想了许多优化的方法。但你现在需要做的,只是判断某个解是否
合法。简单吧?

输入格式
输入的第一行是数字T,表示输入文件含有T个case。之后每个case有9行,每行9个数字(1到9),表示一个数独的解。

输出格式
如果这个解是合法的,输出YES,否则输出NO。(全大写)

输入样例
2
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
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
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
9 8 5 7 4 2 1 6 3
7 3 1 9 8 6 5 4 2
6 2 4 3 5 1 7 9 8
1 6 3 2 7 4 9 8 5
2 4 7 8 9 5 3 1 6
8 5 9 6 1 3 2 7 4
5 9 6 4 2 7 8 3 1
4 1 8 5 3 9 6 2 7
3 7 2 1 6 8 4 5 9

输出样例
NO
YES


解题思路

爆破(设当运用goto还是很方便的)

#include<stdio.h>
#include<string.h>
int main()
{
    int t, f, num[9][9], r_flag[10], c_flag[10];
    scanf("%d", &t);
    while(t --)
    {
        f = 0;
        for(int i = 0; i < 9; i ++)
            for(int j = 0;j < 9; j ++)
                scanf("%d", &num[i][j]);

        // 横竖一起判断
        for(int i = 0; i < 9; i ++)
        {   
            memset(r_flag, 0, sizeof(r_flag));
            memset(c_flag, 0, sizeof(c_flag));
            for(int j = 0; j < 9; j ++)
            {
                 if(r_flag[num[i][j]] || c_flag[num[j][i]])
                {
                    f = 1;
                    goto F;             
                }
                r_flag[num[i][j]] = c_flag[num[j][i]] = 1;
            }
        }
        // 判断方格
        for(int i = 0; i < 9; i += 3)
            for(int j = 0; j < 9; j +=3)
            {
                memset(r_flag, 0, sizeof(r_flag));
                for(int q = 0; q < 3; q ++)
                    for(int k = 0; k < 3; k ++)
                    {
                        // 借用r_flag
                        if(r_flag[num[i + q][j + k]])
                        {
                            f = 1;
                            goto F;
                        }
                        r_flag[num[i + q][j + k]] = 1;      
                    }       
            }
    F:  if(f)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}   
版权声明:本文为sinat_34200786原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sinat_34200786/article/details/79205100