시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 935 164 76 16.814%

문제

수아는 보물 지도를 얻었다. 보물 지도는 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

힌트

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

W3sicHJvYmxlbV9pZCI6IjI0MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWMwYjBcdWM3NTggXHVkNTc0XHVjODAxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM1NDRcdWIyOTQgXHViY2Y0XHViYjNjIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM1YmJcdWM1YzhcdWIyZTQuIFx1YmNmNFx1YmIzYyBcdWM5YzBcdWIzYzRcdWIyOTQgTipNIFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YWNlMCAxKjFcdWQwNmNcdWFlMzBcdWM3NTggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmNmNFx1YmIzYyBcdWM5YzBcdWIzYzRcdWM3NTggXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWJjMTRcdWIyZTRcdWM3NzRcdWFjNzBcdWIwOTggXHVjMTJjXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yzc3NFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWM5YzBcdWIzYzRcdWM1ZDBcdWIyOTQgXHViY2Y0XHViYjNjXHVhY2ZjIFx1YmQ4MFx1YzBiMFx1Yzc1OCBcdWQ1NzRcdWM4MDFcdWMxMjBcdWM3NTggXHVjNzA0XHVjZTU4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjIFx1YzIxOFx1YzU0NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzljMFx1YjNjNFx1YzVkMCBcdWQ0NWNcdWMyZGNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MCBcdWM3NzRcdWM4MWMsIFx1YzIxOFx1YzU0NFx1YjI5NCBcdWJjZjRcdWJiM2NcdWM3NDQgXHVhYzAwXHVjOWMwXHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjODE1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhY2JkXHViODVjXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWMyMThcdWM1NDRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YmNmNFx1YmIzY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHViMDVkXHViMDk4XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViOWU0XHViYzg4IFx1YzIxOFx1YzU0NFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjLCBcdWMyMThcdWM1NDRcdWIyOTQgXHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNjdjXHVjYWJkIFx1YzkxMVx1Yzc1OCBcdWQ1NWMgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1YzEyY1x1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWFjMDBcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmQ4MFx1YzBiMFx1Yzc1OCBcdWQ1NzRcdWM4MDFcdWIzYzQgXHVjMjE4XHVjNTQ0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YWM4M1x1Yzc3NFx1YmJjMFx1Yjg1YywgXHViZDgwXHVjMGIwXHVjNzU4IFx1ZDU3NFx1YzgwMVx1Yzc0NCBcdWM4NzBcdWMyZWNcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI5ZTRcdWJjODggXHVjMjE4XHVjNTQ0XHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWQ2YzRcdWM1ZDAsIFx1ZDU3NFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM1NDRcdWM3NTggXHVjNzc0XHViM2Q5XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NjBcdWM5YzAgXHViYTQ4XHVjZGIwXHVjNzg4XHVjNzQ0XHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWMyMThcdWM1NDRcdWM3NTggXHVjNmMwXHVjOWMxXHVjNzg0XHVhY2ZjIFx1ZDU3NFx1YzgwMVx1Yzc1OCBcdWJjMThcdWM3NTFcdWM3NDQgXHVkMTM0XHVjNzc0XHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3NFx1YmE3NCwgXHViOWU0IFx1ZDEzNFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHVkNmM0XHVjNWQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgMlx1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWNcdWQ2NTVcdWM3NzhcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWI5Y2NcdWM1N2QgXHVjMjE4XHVjNTQ0XHVhYzAwIFx1ZDU3NFx1YzgwMVx1YWNmYyBcdWJjMTRcdWI3N2NcdWJjZjRcdWFjZTAgXHVjNzg4XHViMmU0XHViYTc0IChcdWQ1NzRcdWM4MDFcdWFjZmMgXHVjMjE4XHVjOWMxXHVjMTIwLCBcdWMyMThcdWQzYzlcdWMxMjBcdWMwYzFcdWM1ZDAgXHVjMjE4XHVjNTQ0XHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVjNjI0XHVjOWMxIFx1YWRmOCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViYzE0XHViMmU0XHViOWNjIFx1Yzc4OFx1Yzc0NCBcdWI1NGMpIFx1YzIxOFx1YzU0NFx1YjI5NCBcdWM4ZmRcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCwgXHVjMjE4XHVjNTQ0XHVhYzAwIFx1YzU0NFx1YzljMSBcdWM4ZmRcdWM5YzAgXHVjNTRhXHVjNTU4XHVhY2UwLCBcdWJjZjRcdWJiM2MgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVjMjE4XHVjNTQ0XHViMjk0IFx1YmNmNFx1YmIzY1x1Yzc0MCBcdWM1YmJcdWM3NDAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YmQ4MFx1YzBiMFx1Yzc1OCBcdWQ1NzRcdWM4MDFcdWM3NzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YWM3NCBcdWFkMDBcdWFjYzRcdWM1YzZcdWM3NzQgXHVjMjE4XHVjNTQ0XHVhYzAwIFx1YzhmZFx1YzljMFx1YzU0YVx1YWNlMCBcdWJjZjRcdWJiM2NcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHViODVjXHViOTdjIFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YmNmNFx1YmIzYyBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIE1cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTRcdWIzNzAsIC5cdWM3NDAgXHViYzE0XHViMmU0XHVjNzc0XHVhY2UwLCBJXHViMjk0IFx1YzEyY1x1Yzc3NFx1YWNlMCwgVlx1YjI5NCBcdWQ1NzRcdWM4MDFcdWM3NTggXHVjNzA0XHVjZTU4XHVjNzc0XHVhY2UwLCBZXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWMyMThcdWM1NDRcdWM3NTggXHVjNzA0XHVjZTU4XHVjNzc0XHVhY2UwLCBUXHViMjk0IFx1YmNmNFx1YmIzY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NzRcdWIyZTQuIFYsIFksIFRcdWIyOTQgXHViYWE4XHViNDUwIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHViNGYxXHVjN2E1XHVkNTVjXHViMmU0LiAoMSAmbGU7IE4sIE0gJmxlOyA3MDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMThcdWM1NDRcdWFjMDAgXHViY2Y0XHViYjNjXHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFlFU1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgTk9cdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM1NDRcdWI3OTggXHVjNTQ0XHViNzk4IFx1YzU0NFx1Yjc5OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQgXHVjMjE4XHVjNTQ0XHViMjk0IFx1YmNmNFx1YmIzY1x1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MjQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmVhc3VyZXMgYW5kIFZpa2luZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBoYXZlIGEgdHJlYXN1cmUgbWFwIHRoYXQgaXMgYXJyYW5nZWQgaW50byBhIE4gJnRpbWVzOyBNIGdyaWQuIEEgZ3JpZCBzcXVhcmUgbWF5IGJlIGVpdGhlciBzZWEgb3IgcGFydCBvZiBhbiBpc2xhbmQuIEluIGFkZGl0aW9uLCB0aGUgbWFwIHNob3dzIHRoZSB0cmVhc3VyZSBhbmQgYW4gZW5lbXkgVmlraW5nIHNoaXAgdGhhdCBvY2N1cGllcyBvbmUgKHNlYSkgc3F1YXJlLiBGaW5hbGx5LCBmb3IgY29udmVuaWVuY2UgeW91IGhhdmUgYWxzbyBkcmF3biB5b3VyIG93biBwb3NpdGlvbi48XC9wPlxyXG5cclxuPHA+Tm93IHlvdSBtdXN0IHNldCB1cCBhIFx1ZmIwMXhlZCByb3V0ZSB0byBnZXQgdGhlIHRyZWFzdXJlLiBUaGUgcm91dGUgbXVzdCBzdGFydCBhdCB5b3VyIHBvc2l0aW9uLCBlbmQgYXQgdGhlIHRyZWFzdXJlLCBhbmQgY29uc2lzdCBvZiBhIHNlcXVlbmNlIG9mIG1vdmVzLiBJbiBlYWNoIG1vdmUsIHlvdSBjYW4gZ28gb25seSB0byBhbiAoaG9yaXpvbnRhbGx5IG9yIHZlcnRpY2FsbHkpIGFkamFjZW50IHNxdWFyZSB0aGF0IGlzIG5vdCBwYXJ0IG9mIGFuIGlzbGFuZC4gQnV0IGJld2FyZTogVGhlIFZpa2luZyBzaGlwIG1pZ2h0IGZvbGxvdyB5b3UsIHVzaW5nIHRoZSBzYW1lIGtpbmQgb2YgbW92ZXMhIEFmdGVyIGVhY2ggb2YgeW91ciBtb3ZlcyBhY2NvcmRpbmcgdG8geW91ciByb3V0ZSwgdGhlIFZpa2luZyBzaGlwIG1heSBtb3ZlIG9yIG5vdC4gWW91ciBtb3ZlIGFuZCB0aGUgVmlraW5ncyZyc3F1bzsgcmVhY3Rpb24gdG9nZXRoZXIgaXMgY2FsbGVkIGEgcm91bmQuPFwvcD5cclxuXHJcbjxwPkFmdGVyIGV2ZXJ5IHJvdW5kLCB0aGUgZm9sbG93aW5nIGNoZWNrcyBhcmUgbWFkZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JZiB5b3UgYXJlIGluIGxpbmUgd2l0aCB0aGUgVmlraW5nIHNoaXAgKHlvdSBhcmUgaW4gdGhlIHNhbWUgdmVydGljYWwgb3IgaG9yaXpvbnRhbCBsaW5lIGFzIHRoZSBWaWtpbmcgc2hpcCB3aXRoIG9ubHkgc2VhIGJldHdlZW4gdGhlIFZpa2luZyBzaGlwIGFuZCB5b3UpLCB5b3UgYXJlIGRlYWQuPFwvbGk+XHJcblx0PGxpPklmIHlvdSBhcmVuJnJzcXVvO3QgZGVhZCBhbmQgYXQgdGhlIHRyZWFzdXJlLXNwb3QsIHlvdSBnZXQgdGhlIHRyZWFzdXJlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRlY2lkZXMgd2hldGhlciBpdCBpcyBwb3NzaWJsZSB0byBzZXQgdXAgYSBcdWZiMDF4ZWQgcm91dGUgaW4gYWR2YW5jZSBzdWNoIHRoYXQgeW91IGNhbiBnZXQgdGhlIHRyZWFzdXJlIGJ5IGZvbGxvd2luZyB0aGlzIHJvdXRlIGFuZCB3aWxsIG5vdCBnZXQga2lsbGVkIGJ5IHRoZSBWaWtpbmdzICZuZGFzaDsgbm8gbWF0dGVyIGhvdyB0aGUgVmlraW5nIHNoaXAgbW92ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0sIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBtYXAuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW4gTSBjaGFyYWN0ZXJzLiBFYWNoIGNoYXJhY3RlciBkZXNjcmliZXMgYSBzcXVhcmUgaW4gdGhlIG1hcCwgYW5kIGlzIGVpdGhlciAuIChzZWEpLCBJIChwYXJ0IG9mIGFuIGlzbGFuZCksIFYgKHRoZSBWaWtpbmcgc2hpcCksIFkgKHlvdXIgcG9zaXRpb24pLCBvciBUICh0aGUgdHJlYXN1cmUpLiBFYWNoIG9mIFYsIFksIGFuZCBUIHdpbGwgb2NjdXIgZXhhY3RseSBvbmNlLiZuYnNwOygxICZsZTsgTiwgTSAmbGU7IDcwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBzdHJpbmcgWUVTLCBpZiBpdCBpcyBwb3NzaWJsZSB0byBzZXQgdXAgYSByb3V0ZSB0byBnZXQgdGhlIHRyZWFzdXJlLCBvciBOTyBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBmb2xsb3dpbmcgcm91dGUgd2lsbCBsZXQgeW91IGdldCB0aGUgdHJlYXN1cmU6IERvd24sIERvd24sIERvd24sIFJpZ2h0LCBSaWdodCwgUmlnaHQsIERvd24uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 4번

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