結果

問題 No.157 2つの空洞
ユーザー GrenacheGrenache
提出日時 2016-02-14 11:26:25
言語 Java21
(openjdk 21)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 1,970 bytes
コンパイル時間 3,594 ms
コンパイル使用メモリ 78,372 KB
実行使用メモリ 54,556 KB
最終ジャッジ日時 2024-09-22 06:22:37
合計ジャッジ時間 7,111 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 131 ms
54,132 KB
testcase_01 AC 130 ms
53,940 KB
testcase_02 AC 133 ms
54,216 KB
testcase_03 AC 130 ms
54,300 KB
testcase_04 AC 129 ms
53,940 KB
testcase_05 AC 132 ms
53,908 KB
testcase_06 AC 133 ms
54,012 KB
testcase_07 AC 130 ms
54,308 KB
testcase_08 AC 130 ms
54,164 KB
testcase_09 AC 134 ms
54,196 KB
testcase_10 AC 135 ms
54,236 KB
testcase_11 AC 133 ms
54,260 KB
testcase_12 AC 136 ms
54,400 KB
testcase_13 AC 134 ms
54,280 KB
testcase_14 AC 137 ms
54,092 KB
testcase_15 AC 137 ms
54,128 KB
testcase_16 AC 137 ms
54,556 KB
testcase_17 AC 152 ms
53,972 KB
testcase_18 AC 122 ms
53,112 KB
testcase_19 AC 134 ms
54,232 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