Codeforces Round #301 Div2 C: Ice Cave

問題

codeforces.com

解法

考えなければならないことは以下の2点のみ。

  • ゴールに辿り着けるのか
    • 幅優先探索で調べれば良い。
    • 最短距離で辿り着ければ良いので、一度通ったマスの情報は保存しなくて良い。
  • ゴールに辿り着けたとして、ゴールが壊れにくかった場合、壊してから入れるのか
    • ゴールの周りに、1回目に入る時に通るマスと、ゴールを1回踏んだあとにワンステップ踏むマスの2つの丈夫なマスがあれば良い。

スタートとゴールが隣接しているコーナーケースは別個に考える必要がある。

コード

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	private static int[] start, goal;
	private static final int[][] DIR = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();

		char[][] map = new char[H + 2][];
		map[0] = new char[W + 2];
		map[H + 1] = new char[W + 2];
		Arrays.fill(map[0], 'X');
		Arrays.fill(map[H + 1], 'X');
		for (int i = 1; i <= H; i++) {
			map[i] = ("X" + sc.next() + "X").toCharArray();
		}
		start = new int[2];
		for (int i = 0; i < 2; i++) {
			start[i] = sc.nextInt();
		}
		goal = new int[2];
		for (int i = 0; i < 2; i++) {
			goal[i] = sc.nextInt();
		}
		sc.close();

		// ゴールが割れやすい氷の時
		if (map[goal[0]][goal[1]] == 'X') {
			if (Math.abs(start[0] - goal[0]) + Math.abs(start[1] - goal[1]) == 1) {
				System.out.println("YES");
				return;
			}
			boolean canArrive = false;
			for (int d = 0; d < DIR.length; d++) {
				int x = goal[0] + DIR[d][0];
				int y = goal[1] + DIR[d][1];
				if (map[x][y] == '.') {
					canArrive = true;
					break;
				}
			}
			if (!canArrive) {
				System.out.println("NO");
				return;
			}
		} else {
			int around = 0;
			for (int d = 0; d < DIR.length; d++) {
				int x = goal[0] + DIR[d][0];
				int y = goal[1] + DIR[d][1];
				if (map[x][y] == '.') {
					around++;
				}
			}
			if (Math.abs(start[0] - goal[0]) + Math.abs(start[1] - goal[1]) == 1 && around >= 1) {
				System.out.println("YES");
				return;
			} else if (around < 2) {
				System.out.println("NO");
				return;
			}
		}

		boolean[][] visited = new boolean[H + 2][W + 2];
		Deque<Integer[]> bfsDeque = new ArrayDeque<>();
		bfsDeque.add(new Integer[] { start[0], start[1] });
		visited[start[0]][start[1]] = true;

		while (!bfsDeque.isEmpty()) {
			Integer[] now = bfsDeque.poll();

			for (int d = 0; d < DIR.length; d++) {
				int x = now[0] + DIR[d][0];
				int y = now[1] + DIR[d][1];
				if (x == goal[0] && y == goal[1]) {
					System.out.println("YES");
					return;
				}
				if (map[x][y] == 'X' || visited[x][y]) {
					continue;
				}

				bfsDeque.add(new Integer[] { x, y });
				visited[x][y] = true;
			}
		}
		System.out.println("NO");

	}
}