问题标题: 酷町堂：7087 涂路径

题目描述 Description

小李带领一群同学玩密室逃脱游戏，密室为一个n*m方格的迷宫房间，迷宫有若干墙壁，陷阱和出口，小李每次可以向上，下，左，右其中一个方向移动一格，正常方格用时1秒，陷阱方格用时3秒，但不能移动到墙壁方格。作为队长，小李需要找出最快逃离密室的路径并涂上特殊的荧光粉，以引导其它同学逃离。请你给小李编程求出离开迷宫最少需要多少秒。

输入描述 Input Description

第一行两个正整数n,m(n,m<=1000)。接下来n行，每行m个字符，字符含义如下：
‘.’–该位置可以正常行走方格
‘@’–该位置为迷宫中的陷阱方格
‘#’–该位置为迷宫中的墙壁方格
‘S’–该位置为小李出发的位置方格
‘E’–该位置为迷宫的出口方格

输出描述 Output Description

一行，一个整数，表示逃离密室最短时间，如果小李无法到达出口，输出“The End!!!”

 

这题怕是对bfs有免疫力，竟然WA60

#include<iostream>
#include<queue>
#define inf (1<<25)
using namespace std;
int n,m,sx,sy,ex,ey,ans=inf;
int dir[5][2]={{0},{0,1},{1,0},{-1,0},{0,-1}};
int a[1005][1005],vis[1005][1005];
char op;
struct node{
    int x,y,step;
};
queue<node> q;
void bfs(){
    q.push(node{sx,sy,1});
    vis[sx][sy]=1;
    while(!q.empty()){
        node head=q.front();
        q.pop();
        int x=head.x,y=head.y,step=head.step;
        for(int i=1;i<=4;i++){
            int dx=x+dir[i][0],dy=y+dir[i][1];
            if(dx>=1&&dy>=1&&dx<=n&&dy<=m  &&!vis[dx][dy] && a[dx][dy]!=-1){
                if(dx==ex && dy==ey){
                    ans=min(ans,step);
                }else{
                    q.push(node{dx,dy,step+a[dx][dy]});
                    vis[dx][dy]=1;
                }           
            }
        }
    }
    if(ans==inf) cout<<"The End!!!";
    else cout<<ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>op;
            if(op=='S') sx=i,sy=j;
            else if(op=='E') ex=i,ey=j;
            else if(op=='.') a[i][j]=1;
            else if(op=='@') a[i][j]=3;
            else a[i][j]=-1;
        }
    }
    bfs();
    return 0;
}