注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu1037.Check a Sudoku  

2011-12-16 18:06:39|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1037.Check a Sudoku
Time Limit: 1000 MS         Memory Limit: 65536 K
Total Submissions: 411 (162 users)         Accepted: 193 (152 users)
[ My Solution ]

Description

   Sudoku is a puzzle of a 9×9 grid made up of 3×3 subgrids (called "regions").Some cells already contain numbers, known as "givens". The goal is to fill in the empty cells, one number in each, so that each column, row, and region contains the numbers 1 through 9 exactly once. Each number in the solution therefore occurs only once in each of three "directions", hence the "single numbers" implied by the puzzle's title.
  The attraction of the puzzle is that the completion rules are simple, yet the line of reasoning required to reach the completion may be difficult. Published puzzles often are ranked in terms of difficulty. This also may be expressed by giving an estimated solution time. While, generally speaking, the greater the number of givens, the easier the solution, the opposite is not necessarily true. The true difficulty of the puzzle depends upon how easy it is to logically determine subsequent numbers.
  TheBeet is fond of this game, he has solve lots of sudokus. But one day, when he check the puzzles he had solve before, some of them does not look correct.
  Now TheBeet is busy with his homework. As one of the best programmer in XMU, could you be kind enough to help TheBeet to check the puzzles?

Input

  The first line of the input contains one integer n (n < 20), which represents the number of test cases.
  Each test case contains 9 lines, each line contains 9 integers, which represent the answer to the puzzle you should check.
  There is a blank line after each test case.

Output

  For each test case, output “Case #:” on the first line, '#' is the number of the test case; then you should output“Yes!” (without quotes) if the answer is correct, otherwise you should output “No!”

Sample Input

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

Sample Output

Case 1:
Yes!

Source
厦门大学第四届程序设计竞赛 现场决赛 by TheBeet @ btALT

一次AC,确实挺水的。觉得用字符串来实现比较方便,hash也还不错。。
#include <stdio.h>
#include <string.h>
int sudo[9][9];
int check(int n, int m)
{
        bool hash[9];
        int i, j;
        memset(hash, 0, sizeof(hash));
        for(i = n; i < n+3; i++)
                for(j = m; j < m+3; j++)
                        hash[sudo[i][j]-1] = 1;
        for(i = 0; i < 9; i++)
                if(hash[i] == 0)
                        return 0;
return 1;
}

int main()
{
        int n, i, j, ii;
        bool hash[9];
        scanf("%d", &n);
        for(ii = 1; ii <= n; ii++)
        {
                for(i = 0; i < 9; i++)
                        for(j = 0; j < 9; j++)
                                scanf("%d", &sudo[i][j]);
                int flag = 1;
                for(i = 0; i < 9 && flag; i++)
                {
                        memset(hash, 0, sizeof(hash));
                        for(j = 0; j < 9; j++)
                                hash[sudo[i][j]-1] = 1;
                        for(j = 0; j < 9 && flag; j++)
                                if(hash[j] == 0)
                                        flag = 0;
                        memset(hash, 0, sizeof(hash));
                        for(j = 0; j < 9; j++)
                                hash[sudo[j][i]-1] = 1;
                        for(j = 0; j < 9 && flag; j++)
                                if(hash[j] == 0)
                                        flag = 0;
                }
                flag = (flag && check(0, 0) && check(0,3) && check(0, 6)
                                         && check(3, 0) && check(3,3) && check(3, 6)
                                         && check(6, 0) && check(6,3) && check(6, 6));
                printf("Case %d:\n", ii);
                if(flag == 1)   printf("Yes!\n");
                else    printf("No!\n");
        }
return 0;
}


  评论这张
 
阅读(154)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017