結果

問題 No.157 2つの空洞
ユーザー taku-techtaku-tech
提出日時 2021-06-07 05:55:31
言語 Java21
(openjdk 21)
結果
AC  
実行時間 158 ms / 2,000 ms
コード長 3,111 bytes
コンパイル時間 3,959 ms
コンパイル使用メモリ 79,608 KB
実行使用メモリ 41,520 KB
最終ジャッジ日時 2024-05-03 07:13:28
合計ジャッジ時間 7,744 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 133 ms
41,308 KB
testcase_01 AC 129 ms
41,276 KB
testcase_02 AC 135 ms
41,388 KB
testcase_03 AC 122 ms
40,240 KB
testcase_04 AC 136 ms
41,264 KB
testcase_05 AC 123 ms
40,072 KB
testcase_06 AC 132 ms
41,320 KB
testcase_07 AC 130 ms
41,388 KB
testcase_08 AC 135 ms
41,016 KB
testcase_09 AC 123 ms
40,388 KB
testcase_10 AC 135 ms
41,400 KB
testcase_11 AC 137 ms
41,192 KB
testcase_12 AC 139 ms
41,152 KB
testcase_13 AC 142 ms
41,096 KB
testcase_14 AC 136 ms
41,064 KB
testcase_15 AC 136 ms
41,232 KB
testcase_16 AC 138 ms
41,520 KB
testcase_17 AC 158 ms
41,140 KB
testcase_18 AC 138 ms
41,296 KB
testcase_19 AC 135 ms
41,416 KB
権限があれば一括ダウンロードができます

ソースコード

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