Codeforces Round #301 Div2 C: Ice Cave
解法
考えなければならないことは以下の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"); } }