結果

問題 No.971 いたずらっ子
ユーザー C_nena_EC_nena_E
提出日時 2020-01-17 23:15:12
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 715 ms
73,632 KB
testcase_01 AC 708 ms
74,272 KB
testcase_02 AC 549 ms
67,892 KB
testcase_03 AC 702 ms
72,524 KB
testcase_04 AC 681 ms
67,024 KB
testcase_05 AC 706 ms
73,476 KB
testcase_06 AC 630 ms
68,292 KB
testcase_07 AC 165 ms
41,884 KB
testcase_08 AC 458 ms
52,140 KB
testcase_09 AC 435 ms
52,936 KB
testcase_10 AC 167 ms
41,620 KB
testcase_11 AC 134 ms
40,868 KB
testcase_12 AC 131 ms
41,376 KB
testcase_13 AC 136 ms
41,244 KB
testcase_14 AC 180 ms
42,864 KB
testcase_15 AC 123 ms
40,140 KB
testcase_16 AC 139 ms
41,364 KB
testcase_17 AC 129 ms
41,132 KB
testcase_18 AC 130 ms
41,360 KB
testcase_19 AC 131 ms
41,024 KB
testcase_20 AC 127 ms
41,012 KB
testcase_21 AC 135 ms
41,028 KB
testcase_22 AC 132 ms
40,944 KB
testcase_23 AC 129 ms
41,440 KB
testcase_24 AC 144 ms
41,276 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