前言:

喷死这题,lj死了.出口也有陷阱,大家要小心哦!

思路:

直接bfs+优先队列就好了.

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=3e2+5;
struct xb{
    int x,y;
}st,ed;
struct Q{
    int x,y,step;
    bool operator<(const Q &s)const{
    return step>s.step;
      }
};
vector<xb>v[N][N];
char s[N][N];
bool vis[N][N];
priority_queue<Q>q;
int n,m,t;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int bfs()
{
    while(q.size())
    {
        auto T=q.top();q.pop();
        if(vis[T.x][T.y]||T.x<1||T.x>n||T.y<1||T.y>m||s[T.x][T.y]=='#')    continue;
        if(T.x==ed.x&&T.y==ed.y)    return T.step;
        vis[T.x][T.y]=true;
        for(int i=0;i<4;i++)    q.push({T.x+dx[i],T.y+dy[i],T.step+1});
        for(auto u:v[T.x][T.y])    q.push({u.x,u.y,T.step+3});
    }return -1;
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&t)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%s",s[i]+1);
        while(q.size())    q.pop();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s[i][j]=='S')    st={i,j};
                if(s[i][j]=='T')    ed={i,j};
                vis[i][j]=false;
                v[i][j].clear();
            }
        }q.push({st.x,st.y,0});
        for(int i=1;i<=t;i++)
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++,x2++,y1++,y2++;
            v[x1][y1].push_back({x2,y2});
        }for(auto u:v[st.x][st.y])    q.push({u.x,u.y,3});
        printf("%d\n",bfs());
    }
    return 0;
}