結果

問題 No.157 2つの空洞
ユーザー GrenacheGrenache
提出日時 2016-02-14 11:26:25
言語 Java21
(openjdk 21)
結果
AC  
実行時間 148 ms / 2,000 ms
コード長 1,970 bytes
コンパイル時間 5,906 ms
コンパイル使用メモリ 78,460 KB
実行使用メモリ 57,736 KB
最終ジャッジ日時 2023-10-22 05:08:21
合計ジャッジ時間 7,994 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 140 ms
57,424 KB
testcase_01 AC 135 ms
57,192 KB
testcase_02 AC 135 ms
57,456 KB
testcase_03 AC 138 ms
57,680 KB
testcase_04 AC 139 ms
57,636 KB
testcase_05 AC 138 ms
57,472 KB
testcase_06 AC 140 ms
57,476 KB
testcase_07 AC 135 ms
57,432 KB
testcase_08 AC 139 ms
55,468 KB
testcase_09 AC 139 ms
57,540 KB
testcase_10 AC 138 ms
57,544 KB
testcase_11 AC 136 ms
57,596 KB
testcase_12 AC 137 ms
57,312 KB
testcase_13 AC 138 ms
57,668 KB
testcase_14 AC 148 ms
57,736 KB
testcase_15 AC 142 ms
57,632 KB
testcase_16 AC 139 ms
57,724 KB
testcase_17 AC 148 ms
57,620 KB
testcase_18 AC 139 ms
57,536 KB
testcase_19 AC 144 ms
57,316 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;


public class Main_yukicoder157 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        int w = sc.nextInt();
        int h = sc.nextInt();

        char[][] maze = new char[h][];
        for (int i = 0; i < h; i++) {
        	maze[i] = sc.next().toCharArray();
        }

        int[][] cnt = new int[h][w];

        int x = 0, y = 0;
        out:
        for (x = 0; x < w; x++) {
        	for (y = 0; y < h; y++) {
        		if (maze[y][x] == '.') {
        			break out;
        		}
        	}
        }

        Queue<Integer> qx = new ArrayDeque<Integer>();
        Queue<Integer> qy = new ArrayDeque<Integer>();
        qx.add(x);
        qy.add(y);
        cnt[y][x] = 1;

        while (!qx.isEmpty()) {
        	x = qx.remove();
        	y = qy.remove();

        	for (int i = 0; i < dx.length; i++) {
        		int nx = x + dx[i];
        		int ny = y + dy[i];
        		if (nx < 0 || nx >= w || ny < 0 || ny >= h) {
        			continue;
        		}

        		if (maze[ny][nx] == '#' || cnt[ny][nx] != 0) {
        			continue;
        		}

        		cnt[ny][nx] = 1;
        		qx.add(nx);
        		qy.add(ny);
        	}
        }

        int min = Integer.MAX_VALUE;
        for (int ix = 0; ix < w; ix++) {
        	for (int iy = 0; iy < h; iy++) {
        		if (maze[iy][ix] == '#' || cnt[iy][ix] != 1) {
        			continue;
        		}
                for (int jx = 0; jx < w; jx++) {
                	for (int jy = 0; jy < h; jy++) {
                		if (maze[jy][jx] == '#' || cnt[jy][jx] != 0) {
                			continue;
                		}

                		min = Math.min(min, Math.abs(ix - jx) + Math.abs(iy - jy));
                	}
                }
        	}
        }

        System.out.println(min - 1);

        sc.close();
    }
}
0