시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 995 187 90 17.578%

문제

수아는 보물 지도를 얻었다. 보물 지도는 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+XHVjNTQ0XHViNzk4IFx1YzU0NFx1Yjc5OCBcdWM1NDRcdWI3OTggXHVjNjI0XHViOTc4XHVjYWJkIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNTQ0XHViNzk4IFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1YzIxOFx1YzU0NFx1YjI5NCBcdWJjZjRcdWJiM2NcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNDI0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJlYXN1cmVzIGFuZCBWaWtpbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgaGF2ZSBhIHRyZWFzdXJlIG1hcCB0aGF0IGlzIGFycmFuZ2VkIGludG8gYSBOICZ0aW1lczsgTSBncmlkLiBBIGdyaWQgc3F1YXJlIG1heSBiZSBlaXRoZXIgc2VhIG9yIHBhcnQgb2YgYW4gaXNsYW5kLiBJbiBhZGRpdGlvbiwgdGhlIG1hcCBzaG93cyB0aGUgdHJlYXN1cmUgYW5kIGFuIGVuZW15IFZpa2luZyBzaGlwIHRoYXQgb2NjdXBpZXMgb25lIChzZWEpIHNxdWFyZS4gRmluYWxseSwgZm9yIGNvbnZlbmllbmNlIHlvdSBoYXZlIGFsc28gZHJhd24geW91ciBvd24gcG9zaXRpb24uPFwvcD5cclxuXHJcbjxwPk5vdyB5b3UgbXVzdCBzZXQgdXAgYSBcdWZiMDF4ZWQgcm91dGUgdG8gZ2V0IHRoZSB0cmVhc3VyZS4gVGhlIHJvdXRlIG11c3Qgc3RhcnQgYXQgeW91ciBwb3NpdGlvbiwgZW5kIGF0IHRoZSB0cmVhc3VyZSwgYW5kIGNvbnNpc3Qgb2YgYSBzZXF1ZW5jZSBvZiBtb3Zlcy4gSW4gZWFjaCBtb3ZlLCB5b3UgY2FuIGdvIG9ubHkgdG8gYW4gKGhvcml6b250YWxseSBvciB2ZXJ0aWNhbGx5KSBhZGphY2VudCBzcXVhcmUgdGhhdCBpcyBub3QgcGFydCBvZiBhbiBpc2xhbmQuIEJ1dCBiZXdhcmU6IFRoZSBWaWtpbmcgc2hpcCBtaWdodCBmb2xsb3cgeW91LCB1c2luZyB0aGUgc2FtZSBraW5kIG9mIG1vdmVzISBBZnRlciBlYWNoIG9mIHlvdXIgbW92ZXMgYWNjb3JkaW5nIHRvIHlvdXIgcm91dGUsIHRoZSBWaWtpbmcgc2hpcCBtYXkgbW92ZSBvciBub3QuIFlvdXIgbW92ZSBhbmQgdGhlIFZpa2luZ3MmcnNxdW87IHJlYWN0aW9uIHRvZ2V0aGVyIGlzIGNhbGxlZCBhIHJvdW5kLjxcL3A+XHJcblxyXG48cD5BZnRlciBldmVyeSByb3VuZCwgdGhlIGZvbGxvd2luZyBjaGVja3MgYXJlIG1hZGU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SWYgeW91IGFyZSBpbiBsaW5lIHdpdGggdGhlIFZpa2luZyBzaGlwICh5b3UgYXJlIGluIHRoZSBzYW1lIHZlcnRpY2FsIG9yIGhvcml6b250YWwgbGluZSBhcyB0aGUgVmlraW5nIHNoaXAgd2l0aCBvbmx5IHNlYSBiZXR3ZWVuIHRoZSBWaWtpbmcgc2hpcCBhbmQgeW91KSwgeW91IGFyZSBkZWFkLjxcL2xpPlxyXG5cdDxsaT5JZiB5b3UgYXJlbiZyc3F1bzt0IGRlYWQgYW5kIGF0IHRoZSB0cmVhc3VyZS1zcG90LCB5b3UgZ2V0IHRoZSB0cmVhc3VyZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZWNpZGVzIHdoZXRoZXIgaXQgaXMgcG9zc2libGUgdG8gc2V0IHVwIGEgXHVmYjAxeGVkIHJvdXRlIGluIGFkdmFuY2Ugc3VjaCB0aGF0IHlvdSBjYW4gZ2V0IHRoZSB0cmVhc3VyZSBieSBmb2xsb3dpbmcgdGhpcyByb3V0ZSBhbmQgd2lsbCBub3QgZ2V0IGtpbGxlZCBieSB0aGUgVmlraW5ncyAmbmRhc2g7IG5vIG1hdHRlciBob3cgdGhlIFZpa2luZyBzaGlwIG1vdmVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBNLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgbWFwLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWluIE0gY2hhcmFjdGVycy4gRWFjaCBjaGFyYWN0ZXIgZGVzY3JpYmVzIGEgc3F1YXJlIGluIHRoZSBtYXAsIGFuZCBpcyBlaXRoZXIgLiAoc2VhKSwgSSAocGFydCBvZiBhbiBpc2xhbmQpLCBWICh0aGUgVmlraW5nIHNoaXApLCBZICh5b3VyIHBvc2l0aW9uKSwgb3IgVCAodGhlIHRyZWFzdXJlKS4gRWFjaCBvZiBWLCBZLCBhbmQgVCB3aWxsIG9jY3VyIGV4YWN0bHkgb25jZS4mbmJzcDsoMSAmbGU7IE4sIE0gJmxlOyA3MDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IG11c3QgY29udGFpbiB0aGUgc3RyaW5nIFlFUywgaWYgaXQgaXMgcG9zc2libGUgdG8gc2V0IHVwIGEgcm91dGUgdG8gZ2V0IHRoZSB0cmVhc3VyZSwgb3IgTk8gb3RoZXJ3aXNlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgZm9sbG93aW5nIHJvdXRlIHdpbGwgbGV0IHlvdSBnZXQgdGhlIHRyZWFzdXJlOiBEb3duLCBEb3duLCBEb3duLCBSaWdodCwgUmlnaHQsIFJpZ2h0LCBEb3duLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 4번

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