题意分析

给定一个$M \times N$的网格地图，包含以下元素：

• $'Y'$：坦克的初始位置
• $'T'$：目标位置
• $'S'$：钢铁墙（不可穿过或破坏）
• $'B'$：砖墙（可被射击破坏）
• $'R'$：河流（不可穿过）
• $'E'$：空地（可移动或射击）

坦克每回合可选择：

1. 向相邻$4$方向移动一步（目标需为$'E'$或$'T'$）
2. 向$4$方向之一射击（子弹直线飞行直至出界或击中墙体，击中$'B'$则将其变为$'E'$）

求从$'Y'$到$'T'$的最少回合数，无法到达输出$-1$。

解题思路

1. 状态建模：将坦克位置$(x,y)$和地图状态（被破坏的$'B'$墙）作为搜索状态
2. 优先扩展：使用优先队列（按回合数$step$排序）替代普通队列
3. 射击处理：
   • 子弹路径上遇到$'B'$则立即破坏
   • 遇到$'S'$或$'R'$则停止
4. 移动限制：仅能移动到$'E'$或$'T'$格子

实现步骤

1. 初始化：
   • 记录$'Y'$和$'T'$的坐标
   • 将初始状态$(Y_x, Y_y, 0)$加入优先队列
2. 状态扩展：
   • 移动：检查$4$方向相邻的$'E'$或$'T'$格子
   • 射击：沿$4$方向模拟子弹路径，动态更新被破坏的$'B'$墙
3. 终止条件：
   • 到达$'T'$时返回当前$step$
   • 队列为空时返回$-1$

代码实现

#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int MAXN=300+10;
struct node{
    int x,y,step;
    bool friend operator <(node a,node b){
        return a.step>b.step;
    }
};
char mp[MAXN][MAXN];
int n,m,sx,sy,ex,ey;
int vis[MAXN][MAXN];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void BFS(){
    priority_queue<node> qu;
    memset(vis,0,sizeof(vis));
    node e1;
    e1.x=sx,e1.y=sy,e1.step=0;
    vis[e1.x][e1.y]=1;
    qu.push(e1);
    int ans=-1;
    while(!qu.empty()){
        node e2;
        e1=qu.top();qu.pop();
        if(e1.x==ex&&e1.y==ey){
            ans=e1.step;
            break;
        }
        for(int i=0;i<4;i++){
            e2.x=e1.x+dx[i];
            e2.y=e1.y+dy[i];
            if(!vis[e2.x][e2.y]&&e2.x>=0&&e2.x<n&&e2.y>=0&&e2.y<m&&mp[e2.x][e2.y]!='S'&&mp[e2.x][e2.y]!='R'){
                if(mp[e2.x][e2.y]=='E'||mp[e2.x][e2.y]=='T') e2.step=e1.step+1;
                else{//位置要保持不变，但step要+1
                    e2.step=e1.step+2;
                }
                vis[e2.x][e2.y]=1;
                qu.push(e2);
            }
        }
    }
    printf("%d\n",ans);
}
int main(){
    while(~scanf("%d%d",&n,&m)&&n,m){
        for(int i=0;i<n;i++) scanf("%s",mp[i]);
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mp[i][j]=='Y'){ sx=i;sy=j; }
                if(mp[i][j]=='T'){ ex=i;ey=j; }
            }
        }
        BFS();
    }
    return 0;
}