题解 | #maze#

import java.io.*;
import java.util.*;

public class Main {
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    static class Pos {
        int x;
        int y;
        int time;

        public Pos(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);

        // 符合规则的四个移动方向
        int[][] d = new int[][]{{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
        while (true) {
            String nmq = br.readLine();
            if (nmq == null) {
                break;
            }
            String[] nmqStrArr = nmq.split(" ");
            int n = Integer.parseInt(nmqStrArr[0]), m = Integer.parseInt(nmqStrArr[1]), q = Integer.parseInt(nmqStrArr[2]);
            char[][] maze = new char[n][m];
            int[][] visit = new int[n][m];
            // 开始 结束 位置坐标
            int sx = 0, sy = 0;
            for (int r = 0; r < n; r++) {
                char[] mazeLine = br.readLine().toCharArray();
                for (int c = 0; c < m; c++) {
                    maze[r][c] = mazeLine[c];
                    visit[r][c] = Integer.MAX_VALUE;
                    if (maze[r][c] == 'S') {
                        sx = r;
                        sy = c;
                    } else if (maze[r][c] == '#') {
                        visit[r][c] = -1;
                    }
                }
            }
            // key: 输入位置  x y         val: 输出坐标 x1 y1
            Map<String, List<String>> qMap = new HashMap<>();
            for (int i = 0; i < q; i++) {
                String[] qStr = br.readLine().split(" ");
                // 两端有陷阱的传送没有意义
                if (maze[Integer.parseInt(qStr[0])][Integer.parseInt(qStr[1])] == '#'
                        || maze[Integer.parseInt(qStr[2])][Integer.parseInt(qStr[3])] == '#') {
                    continue;
                }
                String k = qStr[0] + " " + qStr[1];
                String v = qStr[2] + " " + qStr[3];
                if (!qMap.containsKey(k)) {
                    qMap.put(k, new ArrayList<>());
                }
                qMap.get(k).add(v);
            }

            int ans = -1;
            PriorityQueue<Pos> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.time));
            pq.add(new Pos(sx, sy, 0));
            visit[sx][sy] = 0;
            while (!pq.isEmpty()) {
                Pos poll = pq.poll();
                if (maze[poll.x][poll.y] == 'T') {
                    ans = poll.time;
                    break;
                }
                // 四个方向尝试
                for (int i = 0; i < 4; i++) {
                    int nx = poll.x + d[i][0];
                    int ny = poll.y + d[i][1];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || visit[nx][ny] == -1 || poll.time + 1 >= visit[nx][ny]) {
                        continue;
                    }
                    pq.add(new Pos(nx, ny, poll.time + 1));
                    visit[nx][ny] = poll.time + 1;
                }

                // 传送
                String key = poll.x + " " + poll.y;
                if (qMap.containsKey(key)) {
                    List<String> out = qMap.get(key);
                    for (String o : out) {
                        String[] targetPos = o.split(" ");
                        int tx = Integer.parseInt(targetPos[0]);
                        int ty = Integer.parseInt(targetPos[1]);
                        if (poll.time + 3 >= visit[tx][ty]) {
                            continue;
                        }
                        pq.add(new Pos(tx, ty, 3 + poll.time));
                        visit[tx][ty] = poll.time + 3;
                    }
                }
            }
            out.println(ans);
        }
        out.flush();
    }
}