結果

問題 No.157 2つの空洞
ユーザー YamaKasa
提出日時 2018-07-22 12:02:09
言語 Java
(openjdk 23)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 3,058 bytes
コンパイル時間 2,753 ms
コンパイル使用メモリ 78,916 KB
実行使用メモリ 41,636 KB
最終ジャッジ日時 2024-12-26 05:12:11
合計ジャッジ時間 8,265 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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