infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=2676












数独




T了几次终于过了!!代码写得很..纯回溯的。刚开始是正向搜,一直T,看了discuss反向搜就过了!估计是数据问题。

Source Code

Problem: 2676 User: lovecanon
Memory: 224K Time: 79MS
Language: C Result: Accepted

#include<stdio.h>
#include
<string.h>
#include
<stdlib.h>
#include
<math.h>
int map[11][11];
int PlaceIndex[11][11];
int NumOfPlace[11];
int check(int row,int col,int num)
{
    
int i,j;
    
for(i=((int )ceil(1.0*row/3)-1)*3+1;i<=((int )ceil(1.0*row/3))*3;i++)
        
for(j=((int )ceil(1.0*col/3)-1)*3+1;j<=((int )ceil(1.0*col/3))*3;j++)
        {
            
if(map[i][j]==num) return 0;
        }
    
for(i=1;i<=9;i++)
    {
        
if(map[row][i]==num)  return 0;
        
if(map[i][col]==num)   return 0;
    }
    
return 1;
}

int solve(int row,int t)
{
    
int i;
    
if(row<1)  return 1;
    
if(t>NumOfPlace[row]) if(solve(row-1,1)) return 1;
    
for(i=1;i<=9;i++)
    {
        
if(check(row,PlaceIndex[row][t],i))
        {
            map[row][PlaceIndex[row][t]]
=i;
            
if(solve(row,t+1))  return 1;
            map[row][PlaceIndex[row][t]]
=0;
        }
    }
    
return 0;
}

int main()
{
    
int cases;
    scanf(
"%d",&cases);getchar();
    
while(cases--)
    {
        
int i,j;
        memset(NumOfPlace,
0,sizeof(NumOfPlace));

        
for(i=1;i<=9;i++)
        {
            
for(j=1;j<=9;j++)
            {
                map[i][j]
=getchar()-'0';
                
if(map[i][j]==0)  
                {
                    
++NumOfPlace[i];
                    PlaceIndex[i][NumOfPlace[i]]
=j;
                }            
            }
            getchar();
        }
        solve(
9,1);
        
for(i=1;i<=9;i++)
        {
            
for(j=1;j<=9;j++)
                printf(
"%d",map[i][j]);
            printf(
"\n");
        }    
    }
    
return 0;
}

posted on 2008-09-14 10:20 infinity 阅读(575) 评论(1)  编辑 收藏 引用 所属分类: acm

评论

# re: poj 数独 2008-10-20 16:27 我是谁
顶大牛!  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理