【题解】maze

看了题目感觉bfs好像可以做，但是因为有传送门这个条件又觉得bfs太麻烦了。
同时传送门又很像一条特殊的边，看了看限制，n,m只有300，那就直接建图跑一下最短路就好了。

建图方法：
1.对于每个不为#的点，对于它的上下左右4个点，只要另一个点也不为#，那么建一条边权为1有向边。
2.对于传送门，如果两个点都不为#，那么建一条边权为3的有向边。

然后dijkstra一下就好了，spfa应该也可以吧，不过spfa经常会被卡，所以还是dijkstra稳健。

BFS也是可以做的，只需要用map标记一下传送门，在BFS的时候判断一下就行。（太麻烦了还是最短路好）

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};

int top = 0;
int head[maxn];
char mp[310][310];

struct Edge{
    int to,w,next;
}edge[maxn*4];

void init(){
    top=0;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int w){
    edge[top].w=w;
    edge[top].to=v;
    edge[top].next=head[u];
    head[u]=top++;
}

struct Node{
    int id;ll val;
    Node(int id,ll val):id(id),val(val){
    }
    bool operator <(const Node &bb) const
    {
        return val > bb.val;
    }
};

ll dis[maxn];
int vis[maxn];

void dijk(int st){
    for(int i=0;i<maxn;i++){
        dis[i]=1e18;
    }
    memset(vis,0,sizeof(vis));
    priority_queue<Node> q;
    dis[st]=0;
    q.push(Node(st,0));
    while(!q.empty()){
        int u=q.top().id;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for (int i = head[u]; i != -1; i = edge[i].next)
        {
            int to=edge[i].to;int w=edge[i].w;
            if(dis[to]>dis[u]+w&&!vis[to]){
                dis[to]=dis[u]+w;
                q.push(Node(to,dis[to]));
            }
        }
    }
}

int main(){
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k)){
        init();
        for(int i=1;i<=n;i++){
            scanf("%s",mp[i]+1);
        }
        int stx=0,sty=0;
        int tx=0,ty=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(mp[i][j]=='S'){
                    stx=i;sty=j;
                }
                if(mp[i][j]=='T'){
                    tx=i;ty=j;
                }
                for(int z=0;z<4;z++){
                    int xx=i+dx[z];int yy=j+dy[z];
                    if(xx<1||xx>n||yy<1||yy>m||mp[i][j]=='#'||mp[xx][yy]=='#') continue;
                    int num1=i*m+j;int num2=xx*m+yy;
                    addedge(num1,num2,1);
                }
            }
        }
        for(int i=1;i<=k;i++){
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++;y1++;x2++;y2++;
            if(mp[x1][y1]=='#'||mp[x2][y2]=='#') continue;
            int num1=x1*m+y1;int num2=x2*m+y2;
            addedge(num1,num2,3);
        }
        dijk(stx*m+sty);
        if(vis[tx*m+ty]==0) printf("-1\n");
        else printf("%lld\n",dis[tx*m+ty]);
    }
    return 0;
}