Compete
I can't fall down before I die
C++博客
::
首页
::
联系
::
聚合
::
管理
11 Posts :: 3 Stories :: 2 Comments :: 0 Trackbacks
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(2)
给我留言
查看公开留言
查看私人留言
我参与的团队
随笔档案
2010年8月 (3)
2010年6月 (1)
2010年5月 (3)
2010年4月 (4)
文章档案
2010年8月 (3)
搜索
最新评论
1. re: POJ 2002 (Squares)
cuo de !!!1
--sdafg
2. re: POJ 2719[未登录]
顶
--c
阅读排行榜
1. 2010年ACM-ICPC亚洲区预选赛(646)
2. POJ 3252 (Round Numbers)(497)
3. POJ 1970 五子棋问题(485)
4. POJ1528 Perfection 一道水题,却贡献3WA,就因为一个1,好好看题很重要(373)
5. POJ 2719(353)
评论排行榜
1. POJ 2719(1)
2. POJ 2282 The Counting Problem(0)
3. POJ 2187 Beauty Contest 凸包问题(0)
4. POJ 2014(Flow Layout)(0)
5. POJ2295 A DP Problem 解一元方程(只有加减没有乘除没有括号)(0)
POJ 2676 (Sudoku)经典DFS 500MS 240K
1
#include
<
iostream
>
2
using
namespace
std;
3
int
table[
11
][
11
];
4
5
int
row[
11
][
11
];
6
int
col[
11
][
11
];
7
int
squs[
11
][
11
];
8
int
dfs(
int
r,
int
c);
9
int
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
}
47
int
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
丁立洋
阅读(274)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Copyright @ 丁立洋
Powered by:
.Text
and
ASP.NET
Theme by:
.NET Monster