首页 > 代码库 > [ACM] hdu 1242 【BFS】
[ACM] hdu 1242 【BFS】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1242
参考链接:http://www.acmerblog.com/hdu-1242-Rescue-1605.html
普通队列+bfs确实是蒙对的,因为击败守卫需要消耗时间1,因此普通队列每一次出队列的元素只是步数上最优,但不一定是时间上最优的,这时即使我们把整个迷宫搜完以最小值为最优依然不行,因为每一步处理完成都会把该状态标记为已处理vis[i][j]=1,因此,只要有一步不是最优,就会影响后面的结果。这题的正确做法是优先队列,每一次出队都是出时间最少的,这样可以保证每一步最优,并且一旦搜到目标即可立刻结束。
#include <iostream> #include <queue> #include <cstdio> #include <string> #include <cstring> using namespace std; char map[205][205]; int xx[4] = {1,-1,0,0}; int yy[4] = {0,0,1,-1}; bool visit[205][205]; int n,m; struct point { int x; int y; int step; friend bool operator < (point a, point b) { return a.step > b.step; } }a,b; int bfs() { int flag = 0; memset(visit,false,sizeof(visit)); visit[a.x][a.y] = true; priority_queue<point> q; q.push(a); while(!q.empty()) { b = q.top(); q.pop(); if(map[b.x][b.y] == ‘r‘) { flag = b.step; break; } for(int i = 0; i < 4; i++) { a.x = b.x + xx[i]; a.y = b.y + yy[i]; a.step = b.step + 1; if(!visit[a.x][a.y]&&map[a.x][a.y]!=‘#‘) { visit[a.x][a.y] = true; if(map[a.x][a.y]==‘x‘) a.step = a.step + 1; q.push(a); } } } return flag; } int main() { while(cin>>n>>m) { for(int i=0;i<=n+1;++i) map[i][0]=map[i][m+1]=‘#‘; for(int i=0;i<=m+1;++i) map[0][i]=map[n+1][i]=‘#‘; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin>>map[i][j]; if(map[i][j]==‘a‘) { a.x = i; a.y = j; a.step = 0; } } } int step = bfs(); if(step) { cout<<step<<endl;; } else { cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;; } } return 0; } /* 7 8 #.#####. #.a#..r. #..#x... ..#..#.# #...##.. .#...... ........ */
[ACM] hdu 1242 【BFS】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。