为啥写迪杰斯特拉会挂呢

GoldenStein edited 1 年,5 月前

rt

#include<bits/stdc++.h>
using namespace std;
const int N=205;
struct grid{
    int dist,fi,se;
    bool operator < (const grid &tt) const
    {
        return dist>tt.dist;
    }
};
int n,m;
char g[N][N];
int dis[N][N];
bool vis[N][N];
int sx,sy,tx,ty;
int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
inline bool check(int x,int y)
{
    if(x<1||x>n||y<1||y>m||g[x][y]=='#') 
     return false;
    return true;
}
void bfs()
{
    priority_queue<grid> q;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[sx][sy]=0;
    q.push({0,sx,sy});
    while(q.size())
    {
        grid tmp=q.top();q.pop();
        if(tmp.fi==tx&&tmp.se==ty) 
        {
            printf("%d\n",dis[tx][ty]);
            return ;
        }
        if(vis[tmp.fi][tmp.se]) continue;
        for(int i=0;i<4;i++) 
        {
            int tmpx=tmp.fi+dx[i],tmpy=tmp.se+dy[i];
            if(!check(tmpx,tmpy)) continue;
            int tmpvalue;
            if(g[tmpx][tmpy]=='.') tmpvalue=1;
            else if(g[tmpx][tmpy]=='X') tmpvalue=2;
            if(dis[tmpx][tmpy]>dis[tmp.fi][tmp.se]+tmpvalue)
            {
                dis[tmpx][tmpy]=dis[tmp.fi][tmp.se]+tmpvalue;
                q.push({dis[tmpx][tmpy],tmpx,tmpy});
            }
        }
        vis[tmp.fi][tmp.se]=1;
    }
    printf("impossible\n");
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++) 
         {
             cin>>g[i][j];
             if(g[i][j]=='S') 
             {
                 sx=i;
                 sy=j;
             }
             else if(g[i][j]=='T')
             {
                 tx=i;
                 ty=j;
             }
         }
        bfs();
    }
    return 0;
}

Comments