Compete

I can't fall down before I die
  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 3 Stories :: 2 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜
POJ 2676 (Sudoku）经典DFS 500MS 240K
 1#include<iostream>
 2using namespace std;
 3int table[11][11];
 4
 5int row[11][11];
 6int col[11][11];
 7int squs[11][11];
 8int dfs(int r,int c);
 9int main()
10{
11    int i,j;
12    int t;
13    cin>>t;
14    char temp[11];
15    while(t--)
16    {
17        for(i=0;i<=10;i++)
18        {
19            for(j=0;j<=10;j++)
20            {
21                row[i][j]=0;
22                col[i][j]=0;
23                squs[i][j]=0;
24            }
25        }
26        for(i=0;i<9;i++)
27        {
28            cin>>temp;
29            for(j=0;j<9;j++)
30            {
31                table[i][j]=(int)(temp[j]-'0');
32                row[i][table[i][j]]=1;
33                col[j][table[i][j]]=1;
34                squs[i/3*3+j/3][table[i][j]]=1;
35            }
36        }
37        dfs(0,0);
38        for(i=0;i<9;i++)
39        {
40            for(j=0;j<9;j++)
41                cout<<table[i][j];
42            cout<<endl;
43        }
44    }
45    return 0;
46}
47int dfs(int r,int c)
48{
49    if(r==9) return 1;
50    if(table[r][c]!=0)
51    {
52        if(c==8)
53        {
54            return dfs(r+1,0);
55        }
56        else return dfs(r,c+1);
57    }
58    else
59    {
60        int i;
61        for(i=1;i<=9;i++)
62        {
63            if((row[r][i]==0)&&(col[c][i]==0)&&(squs[r/3*3+c/3][i]==0))
64            {
65                table[r][c]=i;
66                row[r][i]=1;
67                col[c][i]=1;
68                squs[r/3*3+c/3][i]=1;
69
70
71                if(c==8)
72                {
73                    if(dfs(r+1,0)==1)
74                        return 1;
75                    else
76                    {
77                        row[r][i]=0;
78                        col[c][i]=0;
79                        squs[r/3*3+c/3][i]=0;
80                        table[r][c]=0;
81                    }
82                }
83                else 
84                {
85                    if(dfs(r,c+1)==1) return 1;
86                    else
87                    {
88                        row[r][i]=0;
89                        col[c][i]=0;
90                        squs[r/3*3+c/3][i]=0;
91                        table[r][c]=0;
92                    }
93                }
94            }
95        }
96        return 0;
97    }
98}
99
posted on 2010-04-21 10:02 丁立洋 阅读(287) 评论(0)  编辑 收藏 引用

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