結果

問題 No.367 ナイトの転身
ユーザー htensai
提出日時 2020-05-12 10:49:27
言語 Java
(openjdk 23)
結果
AC  
実行時間 982 ms / 2,000 ms
コード長 2,914 bytes
コンパイル時間 2,548 ms
コンパイル使用メモリ 79,536 KB
実行使用メモリ 71,488 KB
最終ジャッジ日時 2024-09-13 04:04:16
合計ジャッジ時間 12,021 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.*;
public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        char[][] field = new char[h][];
        int sr = 0;
        int sx = 0;
        int gr = 0;
        int gc = 0;
        int[][] kCosts = new int[h][w];
        int[][] bCosts = new int[h][w];
        for (int i = 0; i < h; i++) {
            field[i] = sc.next().toCharArray();
            Arrays.fill(kCosts[i], Integer.MAX_VALUE);
            Arrays.fill(bCosts[i], Integer.MAX_VALUE);
            for (int j = 0; j < w; j++) {
                if (field[i][j] == 'S') {
                    sr = i;
                    sx = j;
                } else if (field[i][j] == 'G') {
                    gr = i;
                    gc = j;
                }
            }
        }
        PriorityQueue<Path> queue = new PriorityQueue<>();
        queue.add(new Path(sr, sx, 0, true));
        while (queue.size() > 0) {
            Path p = queue.poll();
            if (p.row < 0 || p.row >= h || p.col < 0 || p.col >= w) {
                continue;
            }
            if (p.isKnight) {
                if (kCosts[p.row][p.col] <= p.value) {
                    continue;
                }
                kCosts[p.row][p.col] = p.value;
            } else {
                if (bCosts[p.row][p.col] <= p.value) {
                    continue;
                }
                bCosts[p.row][p.col] = p.value;
            }
            if (field[p.row][p.col] == 'R') {
                p.isKnight ^= true;
            }
            if (p.isKnight) {
                queue.add(new Path(p.row - 2, p.col - 1, p.value + 1, p.isKnight));
                queue.add(new Path(p.row - 2, p.col + 1, p.value + 1, p.isKnight));
                queue.add(new Path(p.row + 2, p.col - 1, p.value + 1, p.isKnight));
                queue.add(new Path(p.row + 2, p.col + 1, p.value + 1, p.isKnight));
                queue.add(new Path(p.row - 1, p.col - 2, p.value + 1, p.isKnight));
                queue.add(new Path(p.row - 1, p.col + 2, p.value + 1, p.isKnight));
                queue.add(new Path(p.row + 1, p.col - 2, p.value + 1, p.isKnight));
                queue.add(new Path(p.row + 1, p.col + 2, p.value + 1, p.isKnight));
            } else {
                queue.add(new Path(p.row - 1, p.col - 1, p.value + 1, p.isKnight));
                queue.add(new Path(p.row - 1, p.col + 1, p.value + 1, p.isKnight));
                queue.add(new Path(p.row + 1, p.col - 1, p.value + 1, p.isKnight));
                queue.add(new Path(p.row + 1, p.col + 1, p.value + 1, p.isKnight));
            }
        }
        int ans = Math.min(kCosts[gr][gc], bCosts[gr][gc]);
        if (ans == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
    
    static class Path implements Comparable<Path> {
        int row;
        int col;
        int value;
        boolean isKnight;
        
        public Path(int row, int col, int value, boolean isKnight) {
            this.row = row;
            this.col = col;
            this.value = value;
            this.isKnight = isKnight;
        }
        
        public int compareTo(Path another) {
            return value - another.value;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0