結果

問題 No.971 いたずらっ子
ユーザー C_nena_EC_nena_E
提出日時 2020-01-17 23:15:12
言語 Java21
(openjdk 21)
結果
AC  
実行時間 711 ms / 2,000 ms
コード長 3,097 bytes
コンパイル時間 2,251 ms
コンパイル使用メモリ 79,252 KB
実行使用メモリ 73,768 KB
最終ジャッジ日時 2024-04-25 02:03:49
合計ジャッジ時間 10,758 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 711 ms
73,684 KB
testcase_01 AC 621 ms
73,344 KB
testcase_02 AC 558 ms
68,488 KB
testcase_03 AC 542 ms
73,740 KB
testcase_04 AC 571 ms
67,104 KB
testcase_05 AC 640 ms
73,768 KB
testcase_06 AC 554 ms
68,140 KB
testcase_07 AC 147 ms
41,864 KB
testcase_08 AC 401 ms
51,848 KB
testcase_09 AC 353 ms
53,576 KB
testcase_10 AC 131 ms
41,652 KB
testcase_11 AC 112 ms
41,360 KB
testcase_12 AC 104 ms
40,448 KB
testcase_13 AC 135 ms
41,256 KB
testcase_14 AC 159 ms
42,416 KB
testcase_15 AC 118 ms
41,012 KB
testcase_16 AC 124 ms
41,420 KB
testcase_17 AC 109 ms
41,448 KB
testcase_18 AC 99 ms
40,288 KB
testcase_19 AC 119 ms
40,972 KB
testcase_20 AC 108 ms
41,388 KB
testcase_21 AC 100 ms
40,700 KB
testcase_22 AC 102 ms
40,144 KB
testcase_23 AC 112 ms
41,356 KB
testcase_24 AC 108 ms
41,388 KB
権限があれば一括ダウンロードができます

ソースコード

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