부산의 해적

시간 제한1초메모리 제한128 MB

요약
섬이 있는 700x700 격자에서, 매 턴 추적자가 최적으로 움직여도 같은 행이나 열에서 걸리지 않고 보물에 도달할 수 있는지 판별하는 문제입니다.
난이도

어려움10점 중 8점

유형
BFS, 그래프, 게임 이론
정답자
아직 제출이 없습니다

문제

수아는 보물 지도를 얻었다. 지도는 N × M 크기의 격자이며, 각 칸은 바다이거나 섬의 일부이다. 지도에는 보물, 해적선, 수아의 현재 위치가 각각 표시되어 있다.

수아는 현재 위치에서 출발해 보물이 있는 칸에 도착하는 경로를 정해야 한다. 수아는 한 번 이동할 때마다 상하좌우로 인접한 한 칸으로 이동하며, 섬으로는 들어갈 수 없다.

하지만 해적도 같은 방식으로 움직인다. 매 턴은 수아가 먼저 한 칸 이동하고, 그 다음 해적이 한 칸 이동하거나 제자리에 머무르는 순서로 진행된다. 각 턴이 끝난 뒤에는 다음 규칙을 적용한다.

  • 수아와 해적이 같은 행 또는 같은 열에 있고, 두 사람 사이에 섬이 하나도 없다면 수아는 붙잡힌다.
  • 수아가 붙잡히지 않았고 보물이 있는 칸에 있다면 수아는 보물을 얻는다.

해적이 어떻게 움직이더라도 수아가 붙잡히지 않고 보물을 얻을 수 있는 경로가 있는지 판단하라.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 보물 지도가 주어진다. 각 줄은 M개의 문자로 이루어진다.

  • .: 바다
  • I: 섬
  • V: 해적의 위치
  • Y: 수아의 현재 위치
  • T: 보물의 위치

V, Y, T는 각각 정확히 한 번씩 등장한다.

제한: 1 ≤ N, M ≤ 700

출력

수아가 보물을 얻을 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

힌트

첫 번째 공개 테스트에서는 아래, 아래, 아래, 오른쪽, 오른쪽, 오른쪽, 아래 순서로 이동하면 보물에 도착할 수 있다.

예제3

  1. 예제 1

    입력
    5 7
    Y.....V
    ..I....
    ..IIIII
    .......
    ...T...
    
    예상 출력
    YES
  2. 예제 2

    입력
    5 7
    Y....V.
    ..I....
    ..IIIII
    .......
    ...T...
    
    예상 출력
    NO
    
  3. 예제 3

    입력
    2 3
    .YT
    VII
    
    예상 출력
    NO