結果

問題 No.157 2つの空洞
コンテスト
ユーザー taku-tech
提出日時 2021-06-07 05:55:31
言語 Java
(openjdk 23)
結果
AC  
実行時間 128 ms / 2,000 ms
コード長 3,111 bytes
コンパイル時間 3,223 ms
コンパイル使用メモリ 79,136 KB
実行使用メモリ 41,636 KB
最終ジャッジ日時 2024-11-24 05:09:45
合計ジャッジ時間 6,396 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no_0157;

import java.util.Scanner;

public class TwoHollow01 {

	enum Map {
		HOLLOW1,
		HOLLOW2,
		INNER_WALL,
		OUTER_WALL;
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();

		Map[][] map = new Map[y][x];

		for(int i = 0; i < map.length; i++) {
			String str = sc.next();
			for(int j = 0; j < map[i].length; j++) {
				if(i == 0 || i == map.length-1 || j == 0 || j == map[i].length-1) {
					map[i][j] = Map.OUTER_WALL;
				}
				else if(str.charAt(j) == '#') {
					map[i][j] = Map.INNER_WALL;
				}
				else if(str.charAt(j) == '.') {
					map[i][j] = Map.HOLLOW2;
				}
			}
		}

//		boolean flag = false;
//		for(int i = 0; i < map.length; i++) {
//			for(int j = 0; j < map[i].length; j++) {
//				if(map[i][j] == Map.HOLLOW2) {
//					map = checkHollow(map, i, j);
//					flag = true;
//					break;
//				}
//			}
//			if(flag) {
//				break;
//			}
//		}

		Map[][] newMap = separateHollow(map);

		System.out.println(explore(newMap));
	}

	private static int explore(Map[][] map) {

		int minWall = Integer.MAX_VALUE;
		for(int y1 = 0; y1 < map.length; y1++) {
			for(int x1 = 0; x1 < map[y1].length; x1++) {
				//INNER_WALLが一つでも周りにあるのか。
				if(map[y1][x1] == Map.HOLLOW1) {
					for(int y2 = 0; y2 < map.length; y2++) {
						for(int x2 = 0; x2 < map[y2].length; x2++) {
							if(map[y2][x2] == Map.HOLLOW2) {
								minWall = Math.min(minWall, (Math.abs(y1 - y2) + Math.abs(x1 - x2)) - 1);
							}
						}
					}
				}
			}
		}

		return minWall;
	}

	private static Map[][] separateHollow(Map[][] map){
		boolean flag = false;
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[i].length; j++) {
				if(map[i][j] == Map.HOLLOW2) {
					map = checkHollow(map, i, j);
					flag = true;
					break;
				}
			}
			if(flag) {
				break;
			}
		}
		return map.clone();
	}

	/**
	 * 2つの空洞を分類する。
	 * @param copyMap
	 * @return
	 */
	private static Map[][] checkHollow(Map[][] copyMap,int y, int x) {

		final int LEFT = x - 1;
		final int RIGHT = x + 1;
		final int UP = y - 1;
		final int DOWN = y + 1;

		if(copyMap[y][x] == Map.HOLLOW2) {
			copyMap[y][x] = Map.HOLLOW1;
			copyMap = checkHollow(copyMap, y, x);
		}

		if(copyMap[UP][x] == Map.HOLLOW2) {
			copyMap[UP][x] = Map.HOLLOW1;
			copyMap = checkHollow(copyMap, UP, x);
		}

		if(copyMap[DOWN][x] == Map.HOLLOW2) {
			copyMap[DOWN][x] = Map.HOLLOW1;
			copyMap = checkHollow(copyMap, DOWN, x);
		}

		if(copyMap[y][RIGHT] == Map.HOLLOW2) {
			copyMap[y][RIGHT] = Map.HOLLOW1;
			copyMap = checkHollow(copyMap, y, RIGHT);
		}

		if(copyMap[y][LEFT] == Map.HOLLOW2) {
			copyMap[y][LEFT] = Map.HOLLOW1;
			copyMap = checkHollow(copyMap, y, LEFT);
		}

		return copyMap;
	}

	/**
	 * mapのコピーを作成
	 * @param origin
	 * @return
	 */
//	private static Map[][] deepCopyArray(Map[][] origin) {
//		Map[][] copyMap = new Map[origin.length][origin[0].length];
//		for(int i = 0; i < origin.length; i++) {
//			copyMap[i] = origin[i].clone();
//		}
//		return copyMap;
//
//	}

}
0