GoldenStein edited 2 年前
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;
}