蜗牛の狂奔笔记
对于蜗牛来说,狂奔虽不代表极速,但展现的却是一种拼尽全力的姿态........
pku 3083
2009年8月10日
题目链接:
PKU 3083 Children of the Candy Corn
分类:DFS+BFS
题目分析与算法原型
这题难度也不算太大,但是却写了很久,也调了很久,主要就是顺时针和逆时针的DFS的坐标处理,看了Discuss里面有大牛的代码到了8k,心中不免有些胆颤,于是就多花了时间思考如何写的精简一些,然而事实上也用了将近120行左右代码(算不上精简了),呵呵,主要就是DFS那块(BFS基本没问题),对于每次,我用了两个数组,两个方向(一个是当前的另一个是上次的),作为参数来判断下次的坐标,拿逆时针转的来说,对于当前的点若为‘#’则下次铁定向右转(对于当前方向来说),顺时针的情况刚好相反,个人感觉自己的DFS函数还不够简练,相信有更好的记录方法,呵呵
Code:
1
#include
<
stdio.h
>
2
#include
<
string
.h
>
3
#define
max 45
4
//
left,right,ll,rr数组中下标对应的0,1,2,3分别表示当前方向为上,左(右),下,右(左)
5
int
left[
4
][
2
]
=
{
{
0
,
-
1
}
,
{
1
,
0
}
,
{
0
,
1
}
,
{
-
1
,
0
}
}
;
6
int
right[
4
][
2
]
=
{
{
0
,
1
}
,
{
1
,
0
}
,
{
0
,
-
1
}
,
{
-
1
,
0
}
}
;
7
int
ll[
4
][
2
]
=
{
{
-
1
,
0
}
,
{
0
,
-
1
}
,
{
1
,
0
}
,
{
0
,
1
}
}
;
8
int
rr[
4
][
2
]
=
{
{
-
1
,
0
}
,
{
0
,
1
}
,
{
1
,
0
}
,
{
0
,
-
1
}
}
;
9
int
step[
4
][
2
]
=
{
{
-
1
,
0
}
,
{
1
,
0
}
,
{
0
,
-
1
}
,
{
0
,
1
}
}
,n,w,h,beg[
2
],res1,res2,res3,min,pub;
10
char
map[max][max];
11
bool
flag[max][max];
12
13
struct
node
14
{
15
int
x,y,step;
16
}
queue[max
*
max];
17
18
bool
check(
int
x,
int
y)
19
{
20
if
(x
>=
0
&&
x
<=
h
-
1
&&
y
>=
0
&&
y
<=
w
-
1
)
return
true
;
21
else
return
false
;
22
}
23
//
当前方向 向左或右旋转数组,前进一步,当前方向,上次的方向,当前的坐标
24
void
dfs(
int
d[
4
][
2
],
int
dd[
4
][
2
],
int
now,
int
last,
int
pos[
2
])
25
{
26
int
p[
2
];
27
if
(map[pos[
0
]][pos[
1
]]
==
'
E
'
)
28
{
29
pub
++
;
30
return
;
31
}
32
if
(map[pos[
0
]][pos[
1
]]
==
'
S
'
||
map[pos[
0
]][pos[
1
]]
==
'
.
'
)
33
{
34
pub
++
;
35
p[
0
]
=
pos[
0
]
+
d[now][
0
];
36
p[
1
]
=
pos[
1
]
+
d[now][
1
];
37
dfs(d,dd,(now
+
1
)
%
4
,now,p);
38
}
39
else
if
(map[pos[
0
]][pos[
1
]]
==
'
#
'
||!
check(pos[
0
],pos[
1
]))
40
{
41
int
kk
=
(now
-
1
+
4
)
%
4
;
42
if
(now
==
(last
+
1
)
%
4
)
//
往左转过来的
43
{
44
p[
0
]
=
pos[
0
]
-
d[last][
0
]
+
dd[kk][
0
];
45
p[
1
]
=
pos[
1
]
-
d[last][
1
]
+
dd[kk][
1
];
46
}
47
else
if
(now
==
(last
-
1
+
4
)
%
4
)
//
往右转过来的
48
{
49
p[
0
]
=
pos[
0
]
+
d[last][
0
]
+
dd[kk][
0
];
50
p[
1
]
=
pos[
1
]
+
d[last][
1
]
+
dd[kk][
1
];
51
}
52
dfs(d,dd,kk,now,p);
53
}
54
return
;
55
}
56
57
int
bfs()
58
{
59
int
i,front
=
0
,rear
=
1
;
60
queue[
0
].x
=
beg[
0
];
61
queue[
0
].y
=
beg[
1
];
62
queue[
0
].step
=
1
;
63
flag[beg[
0
]][beg[
1
]]
=
true
;
64
while
(front
<
rear)
65
{
66
for
(i
=
0
;i
<
4
;i
++
)
67
{
68
int
x
=
queue[front].x,y
=
queue[front].y;
69
x
+=
step[i][
0
];
70
y
+=
step[i][
1
];
71
if
(
!
flag[x][y]
&&
check(x,y)
&&
map[x][y]
!=
'
#
'
)
72
{
73
flag[x][y]
=
true
;
74
queue[rear].x
=
x;
75
queue[rear].y
=
y;
76
queue[rear].step
=
queue[front].step
+
1
;
77
if
(map[x][y]
==
'
E
'
)
return
queue[rear].step;
78
rear
++
;
79
}
80
}
81
front
++
;
82
}
83
}
84
int
main()
85
{
86
int
i,j,kk;
87
scanf(
"
%d
"
,
&
n);
88
while
(n
--
)
89
{
90
scanf(
"
%d%d
"
,
&
w,
&
h);
91
memset(flag,
false
,
sizeof
(flag));
92
min
=
1
;
93
for
(i
=
0
;i
<
h;i
++
)
94
for
(j
=
0
;j
<
w;j
++
)
95
{
96
scanf(
"
%c
"
,
&
map[i][j]);
97
if
(map[i][j]
==
'
S
'
)
98
{
99
beg[
0
]
=
i;
100
beg[
1
]
=
j;
101
}
102
}
103
if
(beg[
0
]
==
h
-
1
)kk
=
0
;
//
上
104
else
if
(beg[
0
]
==
0
)kk
=
1
;
//
下
105
else
if
(beg[
1
]
==
w
-
1
)kk
=
2
;
//
左
106
else
if
(beg[
1
]
==
0
)kk
=
3
;
//
右
107
pub
=
0
;
108
dfs(left,ll,kk,(kk
-
1
+
4
)
%
4
,beg);
109
res1
=
pub;
110
pub
=
0
;
111
if
(kk
==
3
)kk
=
1
;
112
else
if
(kk
==
1
)kk
=
3
;
113
dfs(right,rr,kk,(kk
-
1
+
4
)
%
4
,beg);
114
res2
=
pub;
115
res3
=
bfs();
116
printf(
"
%d %d %d\n
"
,res1,res2,res3);
117
}
118
return
1
;
119
}
120
121
posted on 2009-08-10 18:01
蜗牛也Coding
阅读(316)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 蜗牛也Coding
<
2009年12月
>
日
一
二
三
四
五
六
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
9
导航
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)