結果

問題 No.157 2つの空洞
ユーザー YamaKasaYamaKasa
提出日時 2018-07-22 12:02:09
言語 Java21
(openjdk 21)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 3,058 bytes
コンパイル時間 3,282 ms
コンパイル使用メモリ 76,700 KB
実行使用メモリ 56,632 KB
最終ジャッジ日時 2023-08-27 00:52:24
合計ジャッジ時間 7,063 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 121 ms
55,504 KB
testcase_01 AC 120 ms
55,840 KB
testcase_02 AC 119 ms
56,016 KB
testcase_03 AC 120 ms
56,372 KB
testcase_04 AC 120 ms
56,456 KB
testcase_05 AC 125 ms
53,820 KB
testcase_06 AC 121 ms
55,768 KB
testcase_07 AC 122 ms
55,680 KB
testcase_08 AC 120 ms
55,628 KB
testcase_09 AC 121 ms
55,424 KB
testcase_10 AC 122 ms
56,632 KB
testcase_11 AC 123 ms
55,992 KB
testcase_12 AC 126 ms
56,200 KB
testcase_13 AC 122 ms
55,432 KB
testcase_14 AC 124 ms
55,628 KB
testcase_15 AC 128 ms
56,224 KB
testcase_16 AC 126 ms
55,720 KB
testcase_17 AC 129 ms
55,824 KB
testcase_18 AC 127 ms
55,892 KB
testcase_19 AC 127 ms
55,764 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.awt.Point;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int W = scan.nextInt();
		int H = scan.nextInt();
		int [][]C = new int[H][W];
		int [][]t = new int[H][W];
		int cnt0 = 0;
		int r0 = 0;
		int c0 = 0;
		for(int i = 0; i < H; i++) {
			String s = scan.next();
			for(int j = 0; j < W; j++) {
				if(s.substring(j, j + 1).equals("#")) {
					C[i][j] = 1;
					t[i][j] = 1;
				}else {
					C[i][j] = 0;
					t[i][j] = 0;
					r0 = i;
					c0 = j;
					cnt0 ++;
				}
			}
		}
		scan.close();

		Point start = new Point(c0, r0);
        Deque<Point> stack = new ArrayDeque<Point>();
        stack.push(start);
        int []dr = {1, -1, 0, 0};
        int []dc = {0, 0, 1, -1};

		List<Point> list1 = new ArrayList<Point>();
		list1.add(start);

		while(!stack.isEmpty()) {
           Point temp = stack.pop();
           int tempC = temp.x;
           int tempR = temp.y;
           // System.out.println(tempR + " " + tempC);
            t[tempR][tempC] = 1;
           for(int i = 0; i < 4; i++) {
               int nextR = tempR + dr[i];
               int nextC = tempC + dc[i];
               if(nextC >=0 && nextR >= 0 && nextR < H && nextC < W) {
                  if(t[nextR][nextC] == 0) {
	                Point p = new Point(nextC, nextR);
	                list1.add(p);
	                t[nextR][nextC] = 1;
	                stack.push(p);
                  }
               }
           }
        }

		// ラベル
		loop1:
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				if(t[i][j] == 0) {
					r0 = i;
					c0 = j;
					break loop1;
				}
			}
		}


        start = new Point(c0, r0);
        stack.push(start);

        List<Point> list2 = new ArrayList<Point>();
		list2.add(start);

		while(!stack.isEmpty()) {
           Point temp = stack.pop();
           int tempC = temp.x;
           int tempR = temp.y;
           // System.out.println(tempR + " " + tempC);
            t[tempR][tempC] = 1;
           for(int i = 0; i < 4; i++) {
               int nextR = tempR + dr[i];
               int nextC = tempC + dc[i];
               if(nextC >=0 && nextR >= 0 && nextR < H && nextC < W) {
                  if(t[nextR][nextC] == 0) {
	                Point p = new Point(nextC, nextR);
	                list2.add(p);
	                t[nextR][nextC] = 1;
	                stack.push(p);
                  }
               }
           }
        }
//		for(Point p : list1) {
//			System.out.println(p.y + " " + p.x);
//		}
//		System.out.println();
//		for(Point p : list2) {
//			System.out.println(p.y + " " + p.x);
//		}
		int min = H + W;
		for(Point p1 : list1) {
			for(Point p2 : list2) {
				int l = Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
				if(l == 2) {
					System.out.println(1);
					System.exit(0);
				}
				if(min > l) {
					min = l;
				}
			}
		}
		System.out.println(min - 1);
	}
}
0