Solution 2021-03-01

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution20210301 {
    private static final int[][] next = new int[][]{
            {-1, -2}, {1, -2}, {-1, 2}, {1, 2}, {-2, -1}, {2, -1}, {-2, 1}, {2, 1}
    };
    private static final int INF = Integer.MAX_VALUE >> 1;
    private static final int[] map = new int[250005];
    private static final int[] dist = new int[250005];
    private static final int[] cnt = new int[250005];
    private static int N, M, S, E;

    private static final PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(o -> dist[o]));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            for (int i = 0; i < N; i++) {
                char[] line = br.readLine().toCharArray();
                for (int j = 0; j < M; j++) {
                    int pos = i * M + j;
                    if (line[j] == '.') {
                        map[pos] = 1;
                    } else if (line[j] == '#') {
                        map[pos] = INF;
                    } else if (line[j] == 'R') {
                        map[pos] = 0;
                    } else if (line[j] == 'S') {
                        map[pos] = INF;
                        S = pos;
                    } else if (line[j] == 'E') {
                        map[pos] = 1;
                        E = pos;
                    }
                }
            }
            dijkstra(S);
            if (dist[E] == INF) System.out.println("#" + t + " -1");
            else System.out.println("#" + t + " " + dist[E] + " " + cnt[E]);
        }
    }

    static void dijkstra(int s) {
        Arrays.fill(dist, INF);
        Arrays.fill(cnt, 0);
        pq.add(s);
        dist[S] = 0;
        cnt[S] = 1;
        while (!pq.isEmpty()) {
            int from = pq.poll();
            int x = from / M;
            int y = from % M;
            for (int[] offset : next) {
                int nX = x + offset[0];
                if (nX < 0 || nX >= N) continue;
                int nY = y + offset[1];
                if (nY < 0 || nY >= M) continue;
                int to = nX * M + nY;
                if (dist[to] > dist[from] + map[to]) {
                    dist[to] = dist[from] + map[to];
                    cnt[to] = cnt[from];
                    pq.add(to);
                } else if (dist[to] == dist[from] + map[to]) {
                    cnt[to] += cnt[from];
                    pq.add(to);
                }
            }
        }
    }
}

本文地址：https://blog.csdn.net/awp0011/article/details/114271820