本文主要是介绍hdoj 1180 搜索 + bfs + 优先队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
#include<iostream>
#include<queue>
#define MAX 22
#include<string.h>
using namespace std;struct Node{int x, y, s;friend bool operator<(const Node &a, const Node &b){return a.s > b.s;}
};int vis[MAX][MAX];
char c;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n, m;
int sx, sy;
char map[MAX][MAX];
int check(int x, int y){if(x>=0 && x<n && y>=0 && y<m && !vis[x][y] && map[x][y]!='*')return 1;return 0;
}
Node t1, t2, node;
int bfs(int x, int y){priority_queue<Node> pq;node.x = x; node.y = y; node.s = 0;pq.push(node);vis[node.x][node.y] = 1;//标记已经访问while(!pq.empty()){t1 = pq.top();pq.pop();if(map[t1.x][t1.y] == 'T') return t1.s;//if(map[t2.x][t2.y] == 'T') return t2.s;for(int i = 0; i < 4; ++i){int nx = t1.x + dir[i][0];int ny = t1.y + dir[i][1];if(!check(nx,ny)) continue;t2.x = nx; t2.y = ny; t2.s = t1.s+1;//下一位置是楼梯时候才考虑 否则正常走 //有楼梯时*********************************if(map[nx][ny] == '|' || map[nx][ny] == '-'){if(t2.s%2 == 0){ //这里为偶数步时候 其之前一步的楼梯应该反向 if(map[nx][ny] == '|')c = '-';else if(map[nx][ny] == '-')c = '|'; }elsec = map[nx][ny];t2.x += dir[i][0];t2.y += dir[i][1];if(!check(t2.x,t2.y)) continue;if(c == '|' && (dir[i][1] == 1 || dir[i][1] == -1) || c == '-'&& (dir[i][0] == 1 || dir[i][0] == -1)){t2.s += 1;//c表示到达楼梯前一步时候楼梯所处的状态 } //如果人沿着x（上下）走 楼梯横着 等待//人沿着y（左右）走 楼梯 竖着等待 }//*********************************** vis[t2.x][t2.y] = 1;pq.push(t2);} }//end OF while return -1;
}int main(){while(scanf("%d%d",&n,&m)!=EOF){for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){cin >> map[i][j];if(map[i][j] == 'S'){sx = i; sy = j; }}}memset(vis,0,sizeof(vis));int ans = bfs(sx, sy);printf("%d\n",ans);} return 0;}这篇关于hdoj 1180 搜索 + bfs + 优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
