题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1242
这题很经典,值得敲上20遍,刚开始题目理解错误,超时
原来有多个friend,
注意dfs判段
复制代码
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
/*
HDU 1242 Rescue
http://acm.hdu.edu.cn/showproblem.php?pid=1242
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
const int MAX = 202;
char map[MAX][MAX];
bool visit[MAX][MAX];
int n,m,ax,ay,minx;
int fangxiang[4][2] = {{-1,0},{0,-1},{1,0},{0,1}} ; // // 4个方向 上 左 下 右
bool isCanReach(int x , int y) // 坐标是否合理
{
if(x >= 0 && x < n && y >=0 && y < m)
return true;
return false;
}
void dfs(int x,int y,int len)
{
if(map[x][y] == 'r') // 找到朋友 需要改变最小值
{
if(len < minx)
minx = len;
return;
}else{
if(visit[x][y] || !isCanReach(x,y) || map[x][y] == '#' || len >= minx) // 这里最好加上 len >= minx 判断 ,这样节省时间
return ;
visit[x][y] = true;
for(int i = 0 ; i < 4 ; i ++)
{
int nx = x+fangxiang[i][0];
int ny = y + fangxiang[i][1];
if(map[x][y] == 'x')
{
dfs(nx,ny,len+2);
}else{
dfs(nx,ny,len+1);
}
}
visit[x][y] = false; // 回溯
}
}
int main(){
freopen("in.txt","r",stdin);
int i,j,len;
while(scanf("%d %d%*c",&n,&m)!=EOF)
{
for(i=0;i<n;++i)
{
for(j=0;j<m;++j)
{
visit[i][j] = false;
map[i][j] = getchar();
if(map[i][j]=='a') // 天使的位置
{
ax = i;
ay = j;
}
}
getchar();
}
len = 0;
minx = INT_MAX;
dfs(ax , ay , len);
if(minx != INT_MAX){
printf("%dn",minx);
}else{
printf("Poor ANGEL has to stay in the prison all his life.n");
}
}
return 0;
}
最后
以上就是碧蓝白猫最近收集整理的关于HDU 1242 Rescue - DFS 回溯的全部内容,更多相关HDU内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复