부산의 해적

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

문제

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

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

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

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

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

입력

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

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

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

제한: 1 ≤ N, M ≤ 700

출력

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

힌트

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