蜗牛の狂奔笔记
对于蜗牛来说,狂奔虽不代表极速,但展现的却是一种拼尽全力的姿态........
pku 3009
2009年8月10日
题目链接:
PKU 3009 Curling 2.0
分类:一道经典DFS
题目分析与算法原型
没什么特别讲的,直接dfs,没加什么减枝的情况下,跑了250ms左右(暂时没想到好的剪枝策略).........看到这题之后思路比较清晰,对于每个位置,枚举上,下,左,右四个方向,对于每个方向若没有相邻的障碍物则表示可以从这个方向丢,那么一直从这个方向找,一直到遇到障碍,则从这个障碍的位置继续dfs,若出了板子,表示该方向不可丢,继续下个方向的判断,若当前次数大于10次则返回,若在10之内到达了终点并且所有次数比当前最小的次数还小,则更新最小次数...........
Code:
1
#include
<
stdio.h
>
2
#include
<
string
.h
>
3
#define
len 25
4
#define
max 0x7fffffff
//
0上,1下,2左,3右
5
int
w,h,map[len][len],beg[
2
],min,step[
4
][
2
]
=
{
{
-
1
,
0
}
,
{
1
,
0
}
,
{
0
,
-
1
}
,
{
0
,
1
}
}
;
6
bool
flag[len][len];
7
bool
check(
int
x,
int
y)
8
{
9
if
(x
>=
0
&&
x
<=
h
-
1
&&
y
>=
0
&&
y
<=
w
-
1
)
return
true
;
10
else
return
false
;
11
}
12
void
dfs(
int
count,
int
x,
int
y)
13
{
14
int
i,px,py;
15
if
(count
>
10
)
return
;
16
for
(i
=
0
;i
<
4
;i
++
)
17
{
18
px
=
x
+
step[i][
0
];
19
py
=
y
+
step[i][
1
];
20
21
if
(
!
flag[px][py]
&&
check(px,py))
22
{
23
while
(map[px][py]
!=
3
&&!
flag[px][py]
&&
check(px,py))
24
{
25
px
+=
step[i][
0
];
26
py
+=
step[i][
1
];
27
}
28
if
(check(px,py))
29
{
30
if
(flag[px][py])
31
{
32
flag[px][py]
=
false
;
33
dfs(count
+
1
,px
-
step[i][
0
],py
-
step[i][
1
]);
34
flag[px][py]
=
true
;
35
}
36
else
37
{
38
if
(count
+
1
<=
10
&&
count
<
min)min
=
count
+
1
;
39
return
;
40
}
41
}
42
}
43
}
44
return
;
45
}
46
int
main()
47
{
48
int
i,j;
49
while
(scanf(
"
%d%d
"
,
&
w,
&
h)
!=
EOF)
50
{
51
if
(
!
w
&&!
h)
break
;
52
memset(flag,
false
,
sizeof
(flag));
53
for
(i
=
0
;i
<
h;i
++
)
54
for
(j
=
0
;j
<
w;j
++
)
55
{
56
scanf(
"
%d
"
,
&
map[i][j]);
57
if
(map[i][j]
==
2
)
58
{
59
beg[
0
]
=
i;
60
beg[
1
]
=
j;
61
}
62
else
if
(map[i][j]
==
1
)flag[i][j]
=
true
;
63
}
64
min
=
max;
65
dfs(
0
,beg[
0
],beg[
1
]);
66
if
(min
<
max)printf(
"
%d\n
"
,min);
67
else
printf(
"
-1\n
"
);
68
}
69
return
1
;
70
}
posted on 2009-08-10 20:27
蜗牛也Coding
阅读(236)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 蜗牛也Coding
<
2009年7月
>
日
一
二
三
四
五
六
28
29
30
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
1
2
3
4
5
6
7
8
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 78
文章 - 0
评论 - 96
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔档案
(78)
2011年7月 (1)
2011年4月 (1)
2010年11月 (4)
2010年10月 (4)
2010年9月 (2)
2010年8月 (7)
2010年3月 (1)
2010年2月 (5)
2009年12月 (2)
2009年10月 (1)
2009年9月 (1)
2009年8月 (16)
2009年7月 (31)
2009年6月 (2)
搜索
积分与排名
积分 - 91683
排名 - 259
最新评论
1. re: 关于 OpenGl
太谢谢了。
--袁锋
2. re: 关于 OpenGl
太感谢!
--芙
3. re: 关于MAC系统win 7虚拟机不能上网的问题[未登录]
.vmx文件在哪里?
--a
4. re: MFC中如何将 CFormView放置到一个CDockablePane中
注释掉的创建部分,指针调用
为何不用友元类声明下,就可以用了的。CreateOne,有点绕。
感谢博主分享。
--ren
5. re: 关于 OpenGl
非常感谢~~
--无叶莲
阅读排行榜
1. pragma comment的使用(转)(17177)
2. MFC中如何将 CFormView放置到一个CDockablePane中(8154)
3. (转)关于OpenGL的安装(4821)
4. 关于 OpenGl(4391)
5. VC 界面窗口,静态分割后如何锁定分隔条或限制分隔条的移动范围(4272)
评论排行榜
1. 据说是来自chrome的代码里的一个模板(13)
2. 关于 OpenGl(10)
3. Visual Studio 历史简介(转)(6)
4. pku 1200(6)
5. 推免--北航(5)