結果

問題 No.971 いたずらっ子
ユーザー C_nena_E
提出日時 2020-01-17 23:15:12
言語 Java
(openjdk 23)
結果
AC  
実行時間 715 ms / 2,000 ms
コード長 3,097 bytes
コンパイル時間 2,642 ms
コンパイル使用メモリ 79,312 KB
実行使用メモリ 74,272 KB
最終ジャッジ日時 2024-11-07 11:34:05
合計ジャッジ時間 12,799 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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);
        }
        for(int i = 0; i < w; i++){
            for(int j = 0; j < h; j++){
                if(i == 0 && j == 0){
                    moves[j][i] = 0;
                }else if(i == 0){
                    if (map[j][i] == '.'){
                        moves[j][i] = moves[j-1][i]+1;
                    }else{
                        moves[j][i] = moves[j-1][i]+1+j+i;
                    }
                }else if(j == 0){
                    if (map[j][i] == '.'){
                        moves[j][i] = moves[j][i-1]+1;
                    }else{
                        moves[j][i] = moves[j][i-1]+1+j+i;
                    }
                }else{
                    if (map[j][i] == '.'){
                        moves[j][i] = Math.min(moves[j-1][i],moves[j][i-1])+1;
                    }else{
                        moves[j][i] = Math.min(moves[j-1][i],moves[j][i-1])+1+j+i;
                    }
                }
            }
        }

        /*
        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()];
        return moves[h-1][w-1];
    }
}

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