POJ - 2312 Battle City (bfs + priority

POJ - 2312 Battle City (bfs + priority_queue)

本文主要是介绍POJ - 2312 Battle City (bfs + priority_queue)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题： 传送门
题意： 给你一个地图，各字母含义如下：
Y：你所在的位置
T：目标位置
B：砖头墙（先开炮打碎砖头，花费1，再通过，花费1，一共花费为2）
E：空地（直接通过，花费为1）
S：钢铁墙（不能走）
R：小河（不能走)
题目就是要求从Y到T的最小花费
思路： 直接bfs套上
注意： 由于存在花费不同的情况，所以需要用优先队列把花费小的放在前面
注意： 由于存在花费不同的情况，所以需要用优先队列把花费小的放在前面
注意： 由于存在花费不同的情况，所以需要用优先队列把花费小的放在前面
（重要的事情说三遍）
ps： 本菜鸡由于没有用优先队列wa了几发，枯了

Code：

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX = 307;
int n, m;
char mp[MAX][MAX];
bool vis[MAX][MAX];
struct node {int x, y, dis;bool operator < (const node& other) const{return dis > other.dis;}
};
int d[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
priority_queue<node> q;
bool is_in(int x, int y) {return x >= 0 && x < m && y >= 0 && y < n;
}
int bfs(int x, int y) {vis[x][y] = true;node nd;nd.x=x;nd.y=y;nd.dis=0;q.push(nd);while (!q.empty()) {node u = q.top();q.pop();if (mp[u.x][u.y] == 'T') {return u.dis;}for (int i=0;i<4;i++) {int nx = u.x + d[i][0], ny = u.y + d[i][1];if (is_in(nx, ny) && mp[nx][ny] != 'S' && mp[nx][ny] != 'R' && !vis[nx][ny]) {nd.x = nx;nd.y = ny;if (mp[nx][ny] == 'B') {nd.dis = u.dis + 2;} else {nd.dis = u.dis + 1;}q.push(nd);vis[nx][ny] = true;}}}return -1;
}
void init() {while (!q.empty()) {q.pop();}for (int i=0;i<m;i++)for (int j=0;j<n;j++) {vis[i][j] = false;}
}
int main()
{int sx, sy;while (cin>>m>>n && n && m) {init();for (int i=0;i<m;i++){cin>>mp[i];for (int j=0;j<n;j++) {if (mp[i][j] == 'Y') {sx = i;sy = j;}}}cout<<bfs(sx, sy)<<endl;}return 0;
}