부산의 해적
시간 제한1초메모리 제한128 MB
섬이 있는 700x700 격자에서, 매 턴 추적자가 최적으로 움직여도 같은 행이나 열에서 걸리지 않고 보물에 도달할 수 있는지 판별하는 문제입니다.
문제
수아는 보물 지도를 얻었다. 지도는 N × M 크기의 격자이며, 각 칸은 바다이거나 섬의 일부이다. 지도에는 보물, 해적선, 수아의 현재 위치가 각각 표시되어 있다.
수아는 현재 위치에서 출발해 보물이 있는 칸에 도착하는 경로를 정해야 한다. 수아는 한 번 이동할 때마다 상하좌우로 인접한 한 칸으로 이동하며, 섬으로는 들어갈 수 없다.
하지만 해적도 같은 방식으로 움직인다. 매 턴은 수아가 먼저 한 칸 이동하고, 그 다음 해적이 한 칸 이동하거나 제자리에 머무르는 순서로 진행된다. 각 턴이 끝난 뒤에는 다음 규칙을 적용한다.
- 수아와 해적이 같은 행 또는 같은 열에 있고, 두 사람 사이에 섬이 하나도 없다면 수아는 붙잡힌다.
- 수아가 붙잡히지 않았고 보물이 있는 칸에 있다면 수아는 보물을 얻는다.
해적이 어떻게 움직이더라도 수아가 붙잡히지 않고 보물을 얻을 수 있는 경로가 있는지 판단하라.
입력
첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 보물 지도가 주어진다. 각 줄은 M개의 문자로 이루어진다.
- .: 바다
- I: 섬
- V: 해적의 위치
- Y: 수아의 현재 위치
- T: 보물의 위치
V, Y, T는 각각 정확히 한 번씩 등장한다.
제한: 1 ≤ N, M ≤ 700
출력
수아가 보물을 얻을 수 있으면 YES, 그렇지 않으면 NO를 출력한다.
힌트
첫 번째 공개 테스트에서는 아래, 아래, 아래, 오른쪽, 오른쪽, 오른쪽, 아래 순서로 이동하면 보물에 도착할 수 있다.