首页 > 其他 > 详细

poj 2676

时间:2014-04-07 10:50:33      阅读:488      评论:0      收藏:0      [点我收藏+]

问题描述:

数独问题

解题要点:

回溯时要恢复回溯之前的所有状态,一开始s数组回溯时忘了清零所以结果很奇怪

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<string>
#include<cstring>
 
using namespace std;
const int maxn = 10;
char input[maxn][maxn];
int s[maxn][maxn];
int cubicrecord[maxn][maxn];
int linerecord[maxn][maxn];
int columnrecord[maxn][maxn];
bool success = false;
 
void dfs(int id);
int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int t,i,j,part;
    scanf("%d",&t);
    while(t--)
    {
        success = false;
        memset(cubicrecord,0,sizeof(cubicrecord));
        memset(linerecord,0,sizeof(linerecord));
        memset(columnrecord,0,sizeof(columnrecord));
        memset(s,0,sizeof(s));
        memset(input,0,sizeof(input));
        for(i = 1; i < maxn;++i)
        {
            scanf("%s",input[i]);
            for(j = 1; j < maxn; ++j)
            {  
                s[i][j] = input[i][j-1] - ‘0‘;
                //scanf("%d",s[i]+j);
                part = ((i-1)/3)*3+((j-1)/3+1);
                //p[i][j] = part;
                cubicrecord[part][s[i][j]] = 1;
                linerecord[i][s[i][j]]=1;
                columnrecord[j][s[i][j]]=1;
            }
        }
        /*for(i = 1; i < maxn; ++i){
            for(j = 1; j < maxn;++j){
                printf("%d",p[i][j]);
            }
            printf("\n");
        }
        return 0;*/
        dfs(1);
        for(i = 1; i < maxn; ++i){
            for(j = 1; j < maxn; ++j){
                printf("%d",s[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}
void dfs(int id)
{
    if(success)
        return;
    int x = (id - 1) / 9 + 1;
    int y = (id - 1) % 9 + 1;
    int part =  ((x-1)/3)*3+((y-1)/3+1);
    if(id == 81)
    {
        if(s[x][y])
        {
            success = true;
            return;
        }
        for(int i = 1; i < maxn; ++i)
        {
            if((!linerecord[x][i])&&(!columnrecord[y][i])&&(!cubicrecord[part][i]))
            {
                s[9][9] = i;
                success = true;
                break;
            }
        }
        return;
    }
     
    if(s[x][y])  //这个格子已经填完了
    {
        dfs(id+1);
        if(success)
            return;
    }
    else
    {
        for(int i = 1; i < maxn; ++i)
        {
            if((!linerecord[x][i])&&(!columnrecord[y][i])&&(!cubicrecord[part][i]))
            {
                s[x][y] = i;
                linerecord[x][i] = 1;
                columnrecord[y][i] = 1;
                cubicrecord[part][i] = 1;
                dfs(id+1);
                if(success)
                    break;
                linerecord[x][i] = 0;
                columnrecord[y][i] = 0;
                cubicrecord[part][i] = 0;
                s[x][y] = 0;
            }
        }
        if(success)
            return;
    }
}

  

poj 2676,布布扣,bubuko.com

poj 2676

原文:http://www.cnblogs.com/warmfrog/p/3648456.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!