結果

問題 No.157 2つの空洞
ユーザー YamaKasaYamaKasa
提出日時 2018-07-22 12:02:09
言語 Java21
(openjdk 21)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 3,058 bytes
コンパイル時間 2,502 ms
コンパイル使用メモリ 78,868 KB
実行使用メモリ 54,512 KB
最終ジャッジ日時 2024-06-07 20:12:01
合計ジャッジ時間 6,188 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 141 ms
54,200 KB
testcase_01 AC 136 ms
53,796 KB
testcase_02 AC 137 ms
54,164 KB
testcase_03 AC 136 ms
54,128 KB
testcase_04 AC 137 ms
54,308 KB
testcase_05 AC 140 ms
54,396 KB
testcase_06 AC 136 ms
54,152 KB
testcase_07 AC 135 ms
53,996 KB
testcase_08 AC 143 ms
54,284 KB
testcase_09 AC 145 ms
54,188 KB
testcase_10 AC 136 ms
54,212 KB
testcase_11 AC 142 ms
54,132 KB
testcase_12 AC 139 ms
53,848 KB
testcase_13 AC 140 ms
54,244 KB
testcase_14 AC 152 ms
54,512 KB
testcase_15 AC 140 ms
53,856 KB
testcase_16 AC 142 ms
54,008 KB
testcase_17 AC 148 ms
54,236 KB
testcase_18 AC 140 ms
54,124 KB
testcase_19 AC 137 ms
53,960 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