看题传送门：
ZOJ http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1649
HDU http://acm.hdu.edu.cn/showproblem.php?pid=1242
题目大意初始位置在r，要求到达a的地点，地图上"."通过需要1s，“x"代表守卫，通过耗时2s，“#”不能走。
BFS的应用。
BFS求最短路径的原理是每一次向外扩张一格，（就像树的层次遍历一样），生成的BFS树把同一步数放于同一层，故能保证最优解。
这题变形之处在于，迷宫上有守卫，打到守卫需要1s，才能进入守卫所在的格子。
故不能简单的BFS。
1.
我想到的方法是：
用一个数组记录当前到达的最小步数，如果走过一个格子，下一次走过的时间比较短，那么入队列，更新数组。否则跳过。
2．
看了别人的方法还有：
先在进入守卫所在的地方然后干掉守卫。
如果当前的格子是x则把步数+1，还有把x改为. 并重新入队列。
剩下的就是简单的BFS。
3.
优先队列。。。。Orz大牛。
把队列里面的各个点的步数从小到大，先到达目标的一定是最优的。。。。Orz
方法一：BFS+剪枝。
复制代码
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101#include<cstdio> #include<queue> #include<cstring> using namespace std; const int MAXN=200+10; const int INF=999999; char maze[MAXN][MAXN]; int vis[MAXN][MAXN]; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; int N,M; struct site { int x,y; int step; site(int i,int j,int s){x=i;y=j;step=s;} site(){} }start,en; queue<site> q; void bfs() { q.push(start); int i; while(!q.empty()) { site cur=q.front(); //等下试试temp,而不是q.push(site(nx,ny)); q.pop(); for(i=0;i<4;i++) { int nx=cur.x+dx[i]; int ny=cur.y+dy[i]; int ns=cur.step; if( nx>=0 && ny >=0 && nx < N && ny < M && maze[nx][ny]!='#' ) { if(maze[nx][ny]=='a' && ns+1 < en.step ) { en.step=ns+1; continue; } if(maze[nx][ny]=='.'&& ns + 1 < vis[nx][ny] ) //剪枝 { vis[nx][ny]=ns+1; q.push(site(nx,ny,ns+1)); } if (maze[nx][ny]=='x' && ns + 2 < vis[nx][ny] ) { vis[nx][ny]=ns+2; q.push(site(nx,ny,ns+2)); } } } } } int main() { while(scanf("%d%d",&N,&M)!=EOF) { while(!q.empty()) q.pop(); getchar(); int i,j; for(i=0;i<N;i++) { for(j=0;j<M;j++) { scanf("%c",&maze[i][j]); if(maze[i][j]=='r') { start.x=i; start.y=j; start.step=0; } else if(maze[i][j]=='a') { en.x=i; en.y=j; en.step=INF; } vis[i][j]=INF; } getchar(); } bfs(); if(en.step==INF) printf("Poor ANGEL has to stay in the prison all his life.n"); else printf("%dn",en.step); } }
方法二：先干掉守卫
复制代码
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99#include<cstdio> #include<queue> #include<cstring> using namespace std; const int MAXN=200+10; const int INF=999999; char maze[MAXN][MAXN]; bool vis[MAXN][MAXN]; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; int N,M; struct site { int x,y; int step; site(int i,int j,int s){x=i;y=j;step=s;} site(){} }start,en; queue<site> q; void bfs() { memset(vis,0,sizeof(vis)); q.push(start); int i; while(!q.empty()) { site cur=q.front(); q.pop(); if(maze[cur.x][cur.y]=='x') { maze[cur.x][cur.y]='.'; cur.step++; q.push(cur); continue; } for(i=0;i<4;i++) { int nx=cur.x+dx[i]; int ny=cur.y+dy[i]; int ns=cur.step; if( nx>=0 && ny >=0 && nx < N && ny < M && maze[nx][ny]!='#' &&!vis[nx][ny]) { if(maze[nx][ny]=='a' ) { en.step=ns+1; return; } //此时无需判断是否为x或者.，因为我们是先干掉守卫然后在进入守卫所在的地方。 q.push(site(nx,ny,ns+1)); vis[nx][ny]=true; } } } } int main() { while(scanf("%d%d",&N,&M)!=EOF) { while(!q.empty()) q.pop(); getchar(); int i,j; for(i=0;i<N;i++) { for(j=0;j<M;j++) { scanf("%c",&maze[i][j]); if(maze[i][j]=='r') { start.x=i; start.y=j; start.step=0; } else if(maze[i][j]=='a') { en.x=i; en.y=j; en.step=INF; } } getchar(); } bfs(); if(en.step==INF) printf("Poor ANGEL has to stay in the prison all his life.n"); else printf("%dn",en.step); } }
方法三： 优先队列
复制代码
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#include<cstdio> #include<cstring> #include<queue> using namespace std; const int MAXN=200+10; const int INF=0x3ffffff; char map[MAXN][MAXN]; bool vis[MAXN][MAXN]; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; struct node { int step,x,y; node(){} node(int x,int y,int step): x(x),y(y),step(step){} bool operator < (const node&a)const{ return step>a.step; } }s,e; void bfs() { memset(vis,0,sizeof(vis)); priority_queue<node> q; q.push(s); vis[s.x][s.y]=true; while(!q.empty()) { node cur=q.top(); q.pop(); for(int i=0;i<4;i++) { int nx=cur.x+dx[i],ny=cur.y+dy[i]; if(map[nx][ny]=='a') { e.step=cur.step+1; return; } if(map[nx][ny]!='#'&&!vis[nx][ny]) { if(map[nx][ny]=='x') { q.push(node(nx,ny,cur.step+2)); map[nx][ny]='.'; vis[nx][ny]=true; } else { q.push(node(nx,ny,cur.step+1)); vis[nx][ny]=true; } } } } } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) { scanf("%s",map[i]+1); for(int j=1;j<=m;j++) { if(map[i][j]=='a') { e.x=i;e.y=j;e.step=INF; } if(map[i][j]=='r') { s.x=i;s.y=j;s.step=0; } } } for(int i=0;i<=m+1;i++) map[0][i]=map[n+1][i]='#'; for(int i=0;i<=n+1;i++) map[i][0]=map[i][m+1]='#'; /* for(int i=0;i<=n+1;i++) { for(int j=0;j<=m+1;j++) printf("%c",map[i][j]); printf("n"); }*/ bfs(); if(e.step==INF) puts("Poor ANGEL has to stay in the prison all his life."); else printf("%dn",e.step); } return 0; }
转载于:https://www.cnblogs.com/murmured/p/5004261.html
最后
以上就是鳗鱼书包最近收集整理的关于ZOJ-1649 Rescue BFS (HDU 1242)的全部内容，更多相关ZOJ-1649内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复