通过重新建图，跑一遍最短路可以获得答案。对于二维矩阵的形式，可以考虑转换成一维。
#include<bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=3e5+10; int h[N],ne[N],e[N],w[N],idx; char s[500][500]; int st,ed; int id[5000][5000]; int t; int dis[N]; bool vis[N]; int n,m,qi; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } void dij(){ priority_queue<pll,vector<pll>,greater<pll> > q ; memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); dis[st]=0; q.push({0,st}); while(q.size()){ auto t=q.top(); q.pop(); int pos=t.se; if(pos==ed) break; if(vis[pos]) continue; vis[pos]=1; for(int i=h[pos];i!=-1;i=ne[i]){ int j=e[i]; if(dis[j]>dis[pos]+w[i]){ dis[j]=dis[pos]+w[i]; q.push({dis[j],j}); } } } } void build(){ int i,j; memset(h,-1,sizeof h); int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ for(int u=0;u<4;u++){ int x=i+dx[u],y=j+dy[u]; if(x<=0||x>n||y<=0||y>m) continue; if(s[i][j]=='#'||s[x][y]=='#') continue; int a=id[i][j],b=id[x][y]; add(a,b,1); } } } } int main(){ int t; while(cin>>n>>m>>qi){ int i,j; idx=0; int cnt=0; for(i=1;i<=n;i++){ scanf("%s",s[i]+1); for(j=1;j<=m;j++){ id[i][j]=++cnt; if(s[i][j]=='S') st=id[i][j]; if(s[i][j]=='T') ed=id[i][j]; } } build(); while(qi--){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(s[x1+1][y1+1]=='#'||s[x2+1][y2+1]=='#') continue; int a=id[x1+1][y1+1],b=id[x2+1][y2+1]; add(a,b,3); } dij(); if(dis[ed]==0x3f3f3f3f) cout<<-1<<endl; else cout<<dis[ed]<<endl; } }