結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー 伟国姚
提出日時 2025-07-11 21:56:11
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,079 ms / 3,000 ms
コード長 3,595 bytes
コンパイル時間 5,633 ms
コンパイル使用メモリ 82,740 KB
実行使用メモリ 70,440 KB
最終ジャッジ日時 2025-07-11 21:56:38
合計ジャッジ時間 21,233 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        int m = sc.nextInt(), n = sc.nextInt(), M = sc.nextInt();
        char[][] s = new char[m][n];
        for (int i = 0; i < m; i++) {
            s[i] = sc.next().toCharArray();
        }

        int sx = -1, sy = -1;
        int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        PriorityQueue<int[]> p = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);//x y dis state

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == 'S') {
                    sx = i;
                    sy = j;
                    p.offer(new int[]{sx, sy, 0, 0});
                }
            }
        }
        int[][][] dis = new int[m][n][12];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 12; k++) {
                    dis[i][j][k] = 1 << 30;
                }
            }
        }
        dis[sx][sy][0] = 0;
        int ans = -1;
        o:
        while (!p.isEmpty()) {
            int[] t = p.poll();
            int x = t[0], y = t[1], d = t[2], state = t[3];
            for (int[] dd : dir) {
                int xx = x + dd[0], yy = y + dd[1];
                if (xx < 0 || xx >= m || yy < 0 || yy >= n) continue;
                if (s[xx][yy] == '#') continue;
                if (s[xx][yy] == 'G') {
                    ans = d + 1;
                    break o;
                }
               


                if (s[xx][yy] == '.' || s[xx][yy] == 'S') {
                    if (dis[xx][yy][state] > d + 1) {
                        dis[xx][yy][state] = d + 1;
                        p.offer(new int[]{xx, yy, d + 1, state});
                    }
                }
                if (s[xx][yy] > '0' && s[xx][yy] <= '9') {
                    int digit = s[xx][yy] - '0';
                    if (dis[xx][yy][digit] > d + 1) {
                        dis[xx][yy][digit] = d + 1;
                        p.offer(new int[]{xx, yy, d + 1, digit});
                    }
                }
                if (s[xx][yy] >= 'a' && s[xx][yy] <= 'i') {
                    int idx = s[xx][yy] - 'a' + 1;
                    if (state == idx) {
                        if (dis[xx][yy][state] > d + 1) {
                            dis[xx][yy][state] = d + 1;
                            p.offer(new int[]{xx, yy, d + 1, state});
                        }
                    }
                }

            }


        }

        out.println(ans);

        out.close();
    }

    static Kattio sc = new Kattio();
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    static class Kattio {
        static BufferedReader r;
        static StringTokenizer st;

        public Kattio() {
            r = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(r.readLine());
                }
                return st.nextToken();
            } catch (Exception e) {
                return null;
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}
0