我是靠谱客的博主 碧蓝白猫,这篇文章主要介绍HDU 1242 Rescue - DFS 回溯,现在分享给大家,希望可以做个参考。

题目地址: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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(94)

评论列表共有 0 条评论

立即
投稿
返回
顶部