Battle City

题目链接

题目描述

简单描述一下，细节点击题目链接进行查看。

给定m,n，然后给定m*n的矩阵，矩阵元素由 ‘Y’ (you), ‘T’ (target), ‘S’ (steel wall), ‘B’ (brick wall), ‘R’ (river) and ‘E’ (empty space)中的几个元素组成，并且’Y’和’T’只出现一次，现要求从Y尽快走到T。

其中B表示的位置必须要射击一次，再走一步才算到达，E表示的位置可走一步直接到达，S和R表示的位置不可通过。

解题思路

要求从某点到某点的最短路径想到用bfs，广度优先搜索，最先到达目标地点的路径为最短，但是这个题目与普通的bfs模板略有不同，在这个题目中 每个节点的权值是可能不同的，对于字符为B的位置，它首先需要通过射击打碎障碍，然后再走一步通过。所以就要用到优先队列。

bfs的思路很简单，就是在每一个位置分别向上下左右走一步，然后看这个点是否满足条件（包括是否在地图内，是否已经走过，还有这个点是否可以走），如果满足条件我们就可以走一步，然后将一个节点更新并压入队列。

代码如下

#include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; int m,n; char s[305][305]; bool vis[305][305]; int sx,sy;//Y即开始所在的坐标 int ex,ey;//T即结束的坐标 int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//四个方向 int ans; struct node { int x,y,step; friend bool operator < (node a,node b) { //节点步数少的优先级高。 return a.step > b.step; } }; void bfs() {  priority_queue<node>q;  node start;  start.x = sx;  start.y = sy;  start.step = 0;  vis[sx][sy] = true;  q.push(start); while(!q.empty()) {   node top = q.top();   q.pop(); //printf("top.x = %d,top.y = %dn",top.x,top.y); if(top.x == ex && top.y == ey) {//结束条件 如果不能到达，则ans仍为-1    ans = top.step; return; } for(int i = 0; i < 4; i++) { int x = top.x + dir[i][0]; int y = top.y + dir[i][1]; if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && s[x][y]!='R' && s[x][y]!='S'){        node now = top; if(s[x][y] == 'B') now.step+=2; else now.step++;     now.x = x;     now.y = y;     vis[x][y] = true;     q.push(now); } } } return; } int main() { while(scanf("%d%d",&m,&n)) { if(m==0 && n==0) break; for(int i = 0; i< m; i++) { scanf("%s",s[i]); for(int j = 0; j< n; j++) { if(s[i][j] == 'Y') {      sx = i;      sy = j; } if(s[i][j] == 'T') {      ex = i;      ey = j; } } }   ans = -1; memset(vis,false,sizeof(vis)); //printf("ex = %d,ey = %dn",ex,ey); bfs(); printf("%dn",ans); } }