poj 2676 Sudoku


终于A了
140ms+

说一下我的思路:

接受数据后,把每个为0的位置记录下来(tatus[]),并计算该位置可能的状态数,然后排序,从状态数最小的开始搜索。也就是仅搜索为0的位置。

不过对于这组数据:
9
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
我估计我程序半年都出不了结果

check(x,y,p)函数检查(x,y)位置是否可以放p这个值。
cal()函数计算初始可能的状态数。

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int sudo[10][10];

struct type
{
       int x,y,count;
}status[82]; 
int num_status=0;

bool check(int i, int j, int t)//judge if it is possible to put digit t at (i,j)
{
     for(int k=1; k<=9; k++)
             if(sudo[i][k]==t)return false;
     for(int k=1; k<=9; k++)
             if(sudo[k][j]==t)return false;
     int x=(i-1)/3*3+1 ,y=(j-1)/3*3+1;
     for(int s=0; s<=2; s++)
     for(int tt=0; tt<=2; tt++)
             if(sudo[x+s][y+tt]==t)return false;
     return true;            
}

int cal(int i, int j)//calculate the the number of  possible status of (i,j)
{
    int cnt=0;
    for(int p=1; p<=9; p++)
            if(check(i,j,p))cnt++;
           
    return cnt;
}


bool cmp(const type &a, const type &b)
{
     return a.count<b.count;
}

void dfs(int cnt,bool &find)
{
     if(cnt>num_status)return ;
     if(find){ return ;}
     int x=status[cnt].x;
     int y=status[cnt].y;
    
     if(cnt==num_status)
     {
              for(int p=1; p<=9; p++)
                      if(check(x,y,p))
                      {
                                      sudo[x][y]=p;
                                      for(int i=1; i<=9; i++)
                                      {
                                              for(int j=1; j<=9; j++)
                                                      cout<<sudo[i][j];
                                              cout<<endl;
                                      }
                                      find=true;
                                      return ;
                      }
                      return ;   
     }
     for(int p=1; p<=9; p++)
     {
             if(check(x,y,p))
             {
              sudo[x][y]=p;
              dfs(cnt+1,find);
             }
            sudo[x][y]=0; //刚开始一直错就因为没置0,check函数当当前位置是0的时候才有效。
     }
        
}

 

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
       memset(sudo,0,sizeof sudo);
       char ch;
       num_status=0;
       for(int i=1; i<=9; i++)
               for(int j=1; j<=9; j++)
               {
                cin>>ch;
                sudo[i][j]=int(ch-'0');
                }
               
       for(int i=1; i<=9; i++)
       for(int j=1; j<=9; j++)
                  if(sudo[i][j]==0)
                  {
                      num_status++;
                      status[num_status].x=i; status[num_status].y=j;
                      status[num_status].count=cal(i,j);
                  }
      
       sort(status+1,status+1+num_status,cmp);
      // for(int i=1; i<=num_status ;i++)
        //      cout<<' '<<status[i].x<<' '<<status[i].y<<' '<<status[i].count<<endl;

      
       bool find=false;
       dfs(1,find);
       if(num_status==0)
       {
                    for(int i=1; i<=9; i++)
                    {
                              for(int j=1; j<=9; j++)
                                   cout<<sudo[i][j];
                              cout<<endl;
                    }   
       }
    }
    system("pause");
    return 0;
}


posted on 2010-08-18 19:09 田兵 阅读(179) 评论(2)  编辑 收藏 引用 所属分类: POJ

评论

# re: poj 2676 wa 2010-08-18 20:32 邱焜

阁下代码风格这么好,一定很快就能ac的  回复  更多评论   

# re: poj 2676 Sudoku 2010-08-19 11:33 田兵

@邱焜
拜你吉言,A了 呵呵~~  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜