解题思路

思维转换，从地图起点找终点退出来，因为存在传送机，具体不能一遍普通的bfs跑出来，需要比较细心的处理细节。
那么我们换个角度，如果我们把这个地图里的每个位置当作一个节点，去创建一个图会怎么样呢？
初始化地图输入时，每一个可以转移的小数点，边权是1，这里注意一个细节，别建反图，没什么意义。
q次输入，传送机起点和终点，边权是3。
这样，这个问题就转换成了一个单源最短路，从的单源最短路了。
/---------------------------------------------------------------------------------------------------------------------------------------------------------------/
那么这里是每日一题，我就解释一下求单源最短路算法。
1、无优化的

• 初始化源点
• 找出一个未被标记的，d[x]最小的节点x，然后标记x
• 扫描节点x的所有出边 如果 d[y]>d[x]+z那么更新d[y]=d[x]+z
• 重复上面步骤直到标记n个节点

算法基于贪心思想，只适用于长度都是非负数的图
具体找边这个过程可以用最小堆优化把时间复杂度从

2、带负权边的算法，这里先交代,它已经死过！！！！！！比赛被卡过，所以如果不是负权边，千万别用，不然你会被出题人卡到自闭。
但是它可以用来判断负环（就是一个环的边权和是负数），跑负权边的单源最短路径。都是的优势。
它在我国又被叫做队列优化的算法的时间复杂度一般情况下是k在2左右，最差情况这个也是算法的时间复杂度。
他把迪杰斯特拉算法找最短边，改成了用队头去更新，并且取出的对头，把vis看成0了，这一些图论的代码给出我的整理代码。
我的图论模板
/---------------------------------------------------------------------------------------------------------------------------------------------------------------/

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }

const int N = 305;
const int M = 1e5 + 7; //路径数
const ll INF = 1e18;
char mp[N][N];
ll d1[N * N]; //d1正向图
struct Node { //以前喜欢vector，被卡后发现尽量还是多用用前向星把……
    int v;
    ll cost;
    bool operator < (Node b)const {
        return cost > b.cost;
    }
};
vector<Node> e[N * N];
int n, m, q, st, ed;

void dijkstra(int s, ll d[]) {
    priority_queue<Node>  pq;
    fill(d, d + N*N, INF);
    d[s] = 0;
    pq.push(Node{ s,0 });
    while (!pq.empty()) {
        Node    x = pq.top();
        pq.pop();
        if (d[x.v] < x.cost)    continue; //原先这个节点花费更少 跳过
        for (auto it : e[x.v]) {
            if (d[it.v] > x.cost + it.cost) {
                d[it.v] = x.cost + it.cost;
                pq.push(Node{ it.v,d[it.v] });
            }
        }
    }
}

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

bool check(int x, int y) {
    if (x && x <= n && y && y <= m && mp[x][y] != '#')    return true;
    return false;
}

int main() {
    while (~scanf("%d %d %d", &n, &m, &q)) {
        for (int i = 0; i <= n * m; ++i)    e[i].clear();
        for (int i = 1; i <= n; ++i) {
            scanf("%s", mp[i] + 1);
            for (int j = 1; j <= m; ++j) {
                if (mp[i][j] == 'S')    st = (i - 1) * m + j;
                else if (mp[i][j] == 'T')    ed = (i - 1) * m + j;
            }
        }

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                if (mp[i][j] != '#')
                    for (int k = 0; k < 4; ++k) {
                        int x = i + dx[k], y = j + dy[k];
                        if (check(x, y))
                            e[(i - 1) * m + j].push_back({ (x - 1) * m + y,1 });
                    }
        while (q--) {
            int x = read() + 1, y = read() + 1, u = read() + 1, v = read() + 1;
            if (check(x, y) && check(u, v))
                e[(x - 1) * m + y].push_back({ (u - 1) * m + v, 3 });
        }
        dijkstra(st, d1);
        if (d1[ed] == INF)    puts("-1");
        else
            printf("%lld\n", d1[ed]);
    }
    return 0;
}