結果

問題 No.971 いたずらっ子
コンテスト
ユーザー C_nena_E
提出日時 2020-01-17 22:31:37
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 2,163 bytes
コンパイル時間 2,623 ms
コンパイル使用メモリ 79,600 KB
実行使用メモリ 1,252,972 KB
最終ジャッジ日時 2024-06-25 22:03:55
合計ジャッジ時間 9,986 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        char[][] map = new char[H][];
        for(int i = 0; i < H; i++){
            map[i] = sc.next().toCharArray();
        }
        System.out.println(bfs(H,W,map));
    }

    public static int bfs(int h, int w, char[][]map){
        Point[] D2 = {new Point(1,0), new Point(0,1)};
        int sy = 0;
        int sx = 0;
        int gy = h-1;
        int gx = w-1;
        Point start = new Point(sx, sy), goal = new Point(gx, gy);

        ArrayDeque<Point> dq = new ArrayDeque<>();
        dq.add(start);

        int[][] moves = new int[h][w];
        for(int i = 0; i < h; i++){
            Arrays.fill(moves[i],Integer.MAX_VALUE);
        }
        moves[0][0] = 0;
        map[start.getY()][start.getX()] = '#';

        while (dq.size() > 0) {
            Point p = dq.removeFirst();
            for (int i=0; i<2; i++) {
                int x = p.getX()+D2[i].getX();
                int y = p.getY()+D2[i].getY();
                if(!(0 <= y && y < h && 0 <= x && x < w)){
                    continue;
                }
                else if (map[y][x] == '.') {
                    dq.addLast(new Point(x, y));
                    moves[y][x] = Math.min(moves[y][x],moves[p.getY()][p.getX()] + 1);
                }
                else if (map[y][x] == 'k') {
                    dq.addLast(new Point(x, y));
                    moves[y][x] = Math.min(moves[y][x],(moves[p.getY()][p.getX()] + 1)+y+x);
                }

            }

        }
        /*
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                System.out.print(moves[i][j]+" ");
            }
            System.out.println();
        }
        */
        return moves[goal.getY()][goal.getX()];
    }
}

class Point{

	private int x;
	private int y;

	Point(int a, int b) {x=a; y=b;}

	int getX() {return x;}
	int getY() {return y;}
	void setX(int n) {x = n;}
	void setY(int n) {y = n;}

}
0