시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1062 215 110 19.538%

문제

수아는 보물 지도를 얻었다. 보물 지도는 N*M 크기이고 1*1크기의 정사각형으로 나누어져 있다. 보물 지도의 각 칸은 바다이거나 섬의 일부이다. 그리고, 지도에는 보물과 부산의 해적선의 위치도 있다. 마지막으로 수아는 자신의 위치를 지도에 표시했다.

자 이제, 수아는 보물을 가지기 위한 경로를 정해야 한다. 경로는 현재 수아의 위치에서 시작해야 하고, 보물의 위치에서 끝나야 한다. 매번 수아가 이동할 때, 수아는 위, 아래, 오른쪽, 왼쪽 중의 한 방향으로 이동해야 하고, 섬으로 들어가면 안 된다. 하지만, 부산의 해적도 수아와 같은 방식으로 이동할 것이므로, 부산의 해적을 조심해야 한다. 매번 수아가 이동한 후에, 해적은 수아의 이동에 대해서 이동할지 멈춰있을지 결정할 수 있다. 수아의 움직임과 해적의 반응을 턴이라고 부르면, 매 턴이 지난 후에 다음과 같이 2가지 방법으로확인할 수 있다.

  • 만약 수아가 해적과 바라보고 있다면 (해적과 수직선, 수평선상에 수아가 있고, 오직 그 사이에 바다만 있을 때) 수아는 죽는다.
  • 만약, 수아가 아직 죽지 않았고, 보물 위치에 있다면, 수아는 보물은 얻은 것이다.

부산의 해적이 어떻게 움직이건 관계없이 수아가 죽지않고 보물을 얻을 수 있는 얻을 수 있는 경로를 정하는 프로그램을 작성하시오. 

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 보물 지도가 주어진다. 각 줄은 M개의 문자로 구성되어 있는데, .은 바다이고, I는 섬이고, V는 해적의 위치이고, Y는 현재 수아의 위치이고, T는 보물의 위치이다. V, Y, T는 모두 한 번씩 등장한다. (1 ≤ N, M ≤ 700)

출력

첫째 줄에 수아가 보물을 얻을 수 있으면 YES를 출력하고, 그렇지 않으면 NO를 출력한다.

예제 입력 1

5 7
Y.....V
..I....
..IIIII
.......
...T...

예제 출력 1

YES

힌트

아래 아래 아래 오른쪽 오른쪽 오른쪽 아래 와 같이 움직이면 수아는 보물을 얻을 수 있다.

W3sicHJvYmxlbV9pZCI6IjI0MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWMwYjBcdWM3NTggXHVkNTc0XHVjODAxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM1NDRcdWIyOTQgXHViY2Y0XHViYjNjIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM1YmJcdWM1YzhcdWIyZTQuIFx1YmNmNFx1YmIzYyBcdWM5YzBcdWIzYzRcdWIyOTQgTipNIFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YWNlMCAxKjFcdWQwNmNcdWFlMzBcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmNmNFx1YmIzYyBcdWM5YzBcdWIzYzRcdWM3NTggXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWJjMTRcdWIyZTRcdWM3NzRcdWFjNzBcdWIwOTggXHVjMTJjXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWM5YzBcdWIzYzRcdWM1ZDBcdWIyOTQgXHViY2Y0XHViYjNjXHVhY2ZjIFx1YmQ4MFx1YzBiMFx1Yzc1OCBcdWQ1NzRcdWM4MDFcdWMxMjBcdWM3NTggXHVjNzA0XHVjZTU4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YzIxOFx1YzU0NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzljMFx1YjNjNFx1YzVkMCBcdWQ0NWNcdWMyZGNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MCBcdWM3NzRcdWM4MWMsIFx1YzIxOFx1YzU0NFx1YjI5NCBcdWJjZjRcdWJiM2NcdWM3NDQgXHVhYzAwXHVjOWMwXHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjODE1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhY2JkXHViODVjXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWMyMThcdWM1NDRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YmNmNFx1YmIzY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHViMDVkXHViMDk4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViOWU0XHViYzg4IFx1YzIxOFx1YzU0NFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWMyMThcdWM1NDRcdWIyOTQgXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNjdjXHVjYWJkIFx1YzkxMVx1Yzc1OCBcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YzEyY1x1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWJkODBcdWMwYjBcdWM3NTggXHVkNTc0XHVjODAxXHViM2M0IFx1YzIxOFx1YzU0NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWFjODNcdWM3NzRcdWJiYzBcdWI4NWMsIFx1YmQ4MFx1YzBiMFx1Yzc1OCBcdWQ1NzRcdWM4MDFcdWM3NDQgXHVjODcwXHVjMmVjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViOWU0XHViYzg4IFx1YzIxOFx1YzU0NFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NWMgXHVkNmM0XHVjNWQwLCBcdWQ1NzRcdWM4MDFcdWM3NDAgXHVjMjE4XHVjNTQ0XHVjNzU4IFx1Yzc3NFx1YjNkOVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVjNzc0XHViM2Q5XHVkNTYwXHVjOWMwIFx1YmE0OFx1Y2RiMFx1Yzc4OFx1Yzc0NFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMjE4XHVjNTQ0XHVjNzU4IFx1YzZjMFx1YzljMVx1Yzc4NFx1YWNmYyBcdWQ1NzRcdWM4MDFcdWM3NTggXHViYzE4XHVjNzUxXHVjNzQ0IFx1ZDEzNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzRcdWJhNzQsIFx1YjllNCBcdWQxMzRcdWM3NzQgXHVjOWMwXHViMDljIFx1ZDZjNFx1YzVkMCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IDJcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzNjXHViODVjXHVkNjU1XHVjNzc4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1YzIxOFx1YzU0NFx1YWMwMCBcdWQ1NzRcdWM4MDFcdWFjZmMgXHViYzE0XHViNzdjXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjJlNFx1YmE3NCAoXHVkNTc0XHVjODAxXHVhY2ZjIFx1YzIxOFx1YzljMVx1YzEyMCwgXHVjMjE4XHVkM2M5XHVjMTIwXHVjMGMxXHVjNWQwIFx1YzIxOFx1YzU0NFx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YzYyNFx1YzljMSBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNWQwIFx1YmMxNFx1YjJlNFx1YjljYyBcdWM3ODhcdWM3NDQgXHViNTRjKSBcdWMyMThcdWM1NDRcdWIyOTQgXHVjOGZkXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5Y2NcdWM1N2QsIFx1YzIxOFx1YzU0NFx1YWMwMCBcdWM1NDRcdWM5YzEgXHVjOGZkXHVjOWMwIFx1YzU0YVx1YzU1OFx1YWNlMCwgXHViY2Y0XHViYjNjIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1YzIxOFx1YzU0NFx1YjI5NCBcdWJjZjRcdWJiM2NcdWM3NDAgXHVjNWJiXHVjNzQwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJkODBcdWMwYjBcdWM3NTggXHVkNTc0XHVjODAxXHVjNzc0IFx1YzViNFx1YjViYlx1YWM4YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWFjNzQgXHVhZDAwXHVhY2M0XHVjNWM2XHVjNzc0IFx1YzIxOFx1YzU0NFx1YWMwMCBcdWM4ZmRcdWM5YzBcdWM1NGFcdWFjZTAgXHViY2Y0XHViYjNjXHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM4MTVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWJjZjRcdWJiM2MgXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBNXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0XHViMzcwLCAuXHVjNzQwIFx1YmMxNFx1YjJlNFx1Yzc3NFx1YWNlMCwgSVx1YjI5NCBcdWMxMmNcdWM3NzRcdWFjZTAsIFZcdWIyOTQgXHVkNTc0XHVjODAxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yzc3NFx1YWNlMCwgWVx1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjMjE4XHVjNTQ0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yzc3NFx1YWNlMCwgVFx1YjI5NCBcdWJjZjRcdWJiM2NcdWM3NTggXHVjNzA0XHVjZTU4XHVjNzc0XHViMmU0LiBWLCBZLCBUXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC4gKDEgJmxlOyBOLCBNICZsZTsgNzAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNTQ0XHVhYzAwIFx1YmNmNFx1YmIzY1x1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBZRVNcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTc0IE5PXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNTQ0XHViNzk4IFx1YzU0NFx1Yjc5OCBcdWM1NDRcdWI3OTggXHVjNjI0XHViOTc4XHVjYWJkIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1YzIxOFx1YzU0NFx1YjI5NCBcdWJjZjRcdWJiM2NcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmVhc3VyZXMgYW5kIFZpa2luZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBoYXZlIGEgdHJlYXN1cmUgbWFwIHRoYXQgaXMgYXJyYW5nZWQgaW50byBhIE4gJnRpbWVzOyBNIGdyaWQuIEEgZ3JpZCBzcXVhcmUgbWF5IGJlIGVpdGhlciBzZWEgb3IgcGFydCBvZiBhbiBpc2xhbmQuIEluIGFkZGl0aW9uLCB0aGUgbWFwIHNob3dzIHRoZSB0cmVhc3VyZSBhbmQgYW4gZW5lbXkgVmlraW5nIHNoaXAgdGhhdCBvY2N1cGllcyBvbmUgKHNlYSkgc3F1YXJlLiBGaW5hbGx5LCBmb3IgY29udmVuaWVuY2UgeW91IGhhdmUgYWxzbyBkcmF3biB5b3VyIG93biBwb3NpdGlvbi48XC9wPlxyXG5cclxuPHA+Tm93IHlvdSBtdXN0IHNldCB1cCBhIFx1ZmIwMXhlZCByb3V0ZSB0byBnZXQgdGhlIHRyZWFzdXJlLiBUaGUgcm91dGUgbXVzdCBzdGFydCBhdCB5b3VyIHBvc2l0aW9uLCBlbmQgYXQgdGhlIHRyZWFzdXJlLCBhbmQgY29uc2lzdCBvZiBhIHNlcXVlbmNlIG9mIG1vdmVzLiBJbiBlYWNoIG1vdmUsIHlvdSBjYW4gZ28gb25seSB0byBhbiAoaG9yaXpvbnRhbGx5IG9yIHZlcnRpY2FsbHkpIGFkamFjZW50IHNxdWFyZSB0aGF0IGlzIG5vdCBwYXJ0IG9mIGFuIGlzbGFuZC4gQnV0IGJld2FyZTogVGhlIFZpa2luZyBzaGlwIG1pZ2h0IGZvbGxvdyB5b3UsIHVzaW5nIHRoZSBzYW1lIGtpbmQgb2YgbW92ZXMhIEFmdGVyIGVhY2ggb2YgeW91ciBtb3ZlcyBhY2NvcmRpbmcgdG8geW91ciByb3V0ZSwgdGhlIFZpa2luZyBzaGlwIG1heSBtb3ZlIG9yIG5vdC4gWW91ciBtb3ZlIGFuZCB0aGUgVmlraW5ncyZyc3F1bzsgcmVhY3Rpb24gdG9nZXRoZXIgaXMgY2FsbGVkIGEgcm91bmQuPFwvcD5cclxuXHJcbjxwPkFmdGVyIGV2ZXJ5IHJvdW5kLCB0aGUgZm9sbG93aW5nIGNoZWNrcyBhcmUgbWFkZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JZiB5b3UgYXJlIGluIGxpbmUgd2l0aCB0aGUgVmlraW5nIHNoaXAgKHlvdSBhcmUgaW4gdGhlIHNhbWUgdmVydGljYWwgb3IgaG9yaXpvbnRhbCBsaW5lIGFzIHRoZSBWaWtpbmcgc2hpcCB3aXRoIG9ubHkgc2VhIGJldHdlZW4gdGhlIFZpa2luZyBzaGlwIGFuZCB5b3UpLCB5b3UgYXJlIGRlYWQuPFwvbGk+XHJcblx0PGxpPklmIHlvdSBhcmVuJnJzcXVvO3QgZGVhZCBhbmQgYXQgdGhlIHRyZWFzdXJlLXNwb3QsIHlvdSBnZXQgdGhlIHRyZWFzdXJlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRlY2lkZXMgd2hldGhlciBpdCBpcyBwb3NzaWJsZSB0byBzZXQgdXAgYSBcdWZiMDF4ZWQgcm91dGUgaW4gYWR2YW5jZSBzdWNoIHRoYXQgeW91IGNhbiBnZXQgdGhlIHRyZWFzdXJlIGJ5IGZvbGxvd2luZyB0aGlzIHJvdXRlIGFuZCB3aWxsIG5vdCBnZXQga2lsbGVkIGJ5IHRoZSBWaWtpbmdzICZuZGFzaDsgbm8gbWF0dGVyIGhvdyB0aGUgVmlraW5nIHNoaXAgbW92ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0sIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBtYXAuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW4gTSBjaGFyYWN0ZXJzLiBFYWNoIGNoYXJhY3RlciBkZXNjcmliZXMgYSBzcXVhcmUgaW4gdGhlIG1hcCwgYW5kIGlzIGVpdGhlciAuIChzZWEpLCBJIChwYXJ0IG9mIGFuIGlzbGFuZCksIFYgKHRoZSBWaWtpbmcgc2hpcCksIFkgKHlvdXIgcG9zaXRpb24pLCBvciBUICh0aGUgdHJlYXN1cmUpLiBFYWNoIG9mIFYsIFksIGFuZCBUIHdpbGwgb2NjdXIgZXhhY3RseSBvbmNlLiZuYnNwOygxICZsZTsgTiwgTSAmbGU7IDcwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBzdHJpbmcgWUVTLCBpZiBpdCBpcyBwb3NzaWJsZSB0byBzZXQgdXAgYSByb3V0ZSB0byBnZXQgdGhlIHRyZWFzdXJlLCBvciBOTyBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBmb2xsb3dpbmcgcm91dGUgd2lsbCBsZXQgeW91IGdldCB0aGUgdHJlYXN1cmU6IERvd24sIERvd24sIERvd24sIFJpZ2h0LCBSaWdodCwgUmlnaHQsIERvd24uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 4번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013