시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB137633820525.246%

문제

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

예제 입력 2

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

예제 출력 2

NO

예제 입력 3

2 3
.YT
VII

예제 출력 3

NO

힌트

첫 번째 예제의 경우 아래 아래 아래 오른쪽 오른쪽 오른쪽 아래와 같이 움직이면 수아는 보물을 얻을 수 있다.

W3sicHJvYmxlbV9pZCI6IjI0MjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJkODBcdWMwYjBcdWM3NTggXHVkNTc0XHVjODAxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM1NDRcdWIyOTQgXHViY2Y0XHViYjNjIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM1YmJcdWM1YzhcdWIyZTQuIFx1YmNmNFx1YmIzYyBcdWM5YzBcdWIzYzRcdWIyOTQgTiAmdGltZXM7IE0gXHVkMDZjXHVhZTMwXHVjNzc0XHVhY2UwIDEgJnRpbWVzOyAxXHVkMDZjXHVhZTMwXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJjZjRcdWJiM2MgXHVjOWMwXHViM2M0XHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM3NDAgXHViYzE0XHViMmU0XHVjNzc0XHVhYzcwXHViMDk4IFx1YzEyY1x1Yzc1OCBcdWM3N2NcdWJkODBcdWM3NzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCwgXHVjOWMwXHViM2M0XHVjNWQwXHViMjk0IFx1YmNmNFx1YmIzY1x1YWNmYyBcdWJkODBcdWMwYjBcdWM3NTggXHVkNTc0XHVjODAxXHVjMTIwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWMyMThcdWM1NDRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM5YzBcdWIzYzRcdWM1ZDAgXHVkNDVjXHVjMmRjXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTAgXHVjNzc0XHVjODFjLCBcdWMyMThcdWM1NDRcdWIyOTQgXHViY2Y0XHViYjNjXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVhY2JkXHViODVjXHViOTdjIFx1YzgxNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWQ2MDRcdWM3YWMgXHVjMjE4XHVjNTQ0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWJjZjRcdWJiM2NcdWM3NTggXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YjA1ZFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjllNFx1YmM4OCBcdWMyMThcdWM1NDRcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YywgXHVjMjE4XHVjNTQ0XHViMjk0IFx1YzcwNCwgXHVjNTQ0XHViNzk4LCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YzY3Y1x1Y2FiZCBcdWM5MTFcdWM3NTggXHVkNTVjIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWMxMmNcdWM3M2NcdWI4NWMgXHViNGU0XHVjNWI0XHVhYzAwXHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViZDgwXHVjMGIwXHVjNzU4IFx1ZDU3NFx1YzgwMVx1YjNjNCBcdWMyMThcdWM1NDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVhYzgzXHVjNzc0XHViYmMwXHViODVjLCBcdWJkODBcdWMwYjBcdWM3NTggXHVkNTc0XHVjODAxXHVjNzQ0IFx1Yzg3MFx1YzJlY1x1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjllNFx1YmM4OCBcdWMyMThcdWM1NDRcdWFjMDAgXHVjNzc0XHViM2Q5XHVkNTVjIFx1ZDZjNFx1YzVkMCwgXHVkNTc0XHVjODAxXHVjNzQwIFx1YzIxOFx1YzU0NFx1Yzc1OCBcdWM3NzRcdWIzZDlcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU2MFx1YzljMCBcdWJhNDhcdWNkYjBcdWM3ODhcdWM3NDRcdWM5YzAgXHVhY2IwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YzU0NFx1Yzc1OCBcdWM2YzBcdWM5YzFcdWM3ODRcdWFjZmMgXHVkNTc0XHVjODAxXHVjNzU4IFx1YmMxOFx1Yzc1MVx1Yzc0NCBcdWQxMzRcdWM3NzRcdWI3N2NcdWFjZTAgXHViZDgwXHViOTc0XHViYTc0LCBcdWI5ZTQgXHVkMTM0XHVjNzc0IFx1YzljMFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCAyXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1Y1x1ZDY1NVx1Yzc3OFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCBcdWMyMThcdWM1NDRcdWFjMDAgXHVkNTc0XHVjODAxXHVhY2ZjIFx1YmMxNFx1Yjc3Y1x1YmNmNFx1YWNlMCBcdWM3ODhcdWIyZTRcdWJhNzQgKFx1ZDU3NFx1YzgwMVx1YWNmYyBcdWMyMThcdWM5YzFcdWMxMjAsIFx1YzIxOFx1ZDNjOVx1YzEyMFx1YzBjMVx1YzVkMCBcdWMyMThcdWM1NDRcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWM2MjRcdWM5YzEgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWJjMTRcdWIyZTRcdWI5Y2MgXHVjNzg4XHVjNzQ0IFx1YjU0YykgXHVjMjE4XHVjNTQ0XHViMjk0IFx1YzhmZFx1YjI5NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNTdkLCBcdWMyMThcdWM1NDRcdWFjMDAgXHVjNTQ0XHVjOWMxIFx1YzhmZFx1YzljMCBcdWM1NGFcdWM1NThcdWFjZTAsIFx1YmNmNFx1YmIzYyBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMmU0XHViYTc0LCBcdWMyMThcdWM1NDRcdWIyOTQgXHViY2Y0XHViYjNjXHVjNzQwIFx1YzViYlx1Yzc0MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViZDgwXHVjMGIwXHVjNzU4IFx1ZDU3NFx1YzgwMVx1Yzc3NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjNmMwXHVjOWMxXHVjNzc0XHVhYzc0IFx1YWQwMFx1YWNjNFx1YzVjNlx1Yzc3NCBcdWMyMThcdWM1NDRcdWFjMDAgXHVjOGZkXHVjOWMwXHVjNTRhXHVhY2UwIFx1YmNmNFx1YmIzY1x1Yzc0NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViY2Y0XHViYjNjIFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgTVx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NFx1YjM3MCwgLlx1Yzc0MCBcdWJjMTRcdWIyZTRcdWM3NzRcdWFjZTAsIElcdWIyOTQgXHVjMTJjXHVjNzc0XHVhY2UwLCBWXHViMjk0IFx1ZDU3NFx1YzgwMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NzRcdWFjZTAsIFlcdWIyOTQgXHVkNjA0XHVjN2FjIFx1YzIxOFx1YzU0NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NzRcdWFjZTAsIFRcdWIyOTQgXHViY2Y0XHViYjNjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yzc3NFx1YjJlNC4gViwgWSwgVFx1YjI5NCBcdWJhYThcdWI0NTAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWI0ZjFcdWM3YTVcdWQ1NWNcdWIyZTQuICgxICZsZTsgTiwgTSAmbGU7IDcwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzU0NFx1YWMwMCBcdWJjZjRcdWJiM2NcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzQgWUVTXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjNjA4XHVjODFjXHVjNzU4IFx1YWNiZFx1YzZiMCBcdWM1NDRcdWI3OTggXHVjNTQ0XHViNzk4IFx1YzU0NFx1Yjc5OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzZjMFx1YzljMVx1Yzc3NFx1YmE3NCBcdWMyMThcdWM1NDRcdWIyOTQgXHViY2Y0XHViYjNjXHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjQyNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyZWFzdXJlcyBhbmQgVmlraW5ncyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGhhdmUgYSB0cmVhc3VyZSBtYXAgdGhhdCBpcyBhcnJhbmdlZCBpbnRvIGEgTiAmdGltZXM7IE0gZ3JpZC4gQSBncmlkIHNxdWFyZSBtYXkgYmUgZWl0aGVyIHNlYSBvciBwYXJ0IG9mIGFuIGlzbGFuZC4gSW4gYWRkaXRpb24sIHRoZSBtYXAgc2hvd3MgdGhlIHRyZWFzdXJlIGFuZCBhbiBlbmVteSBWaWtpbmcgc2hpcCB0aGF0IG9jY3VwaWVzIG9uZSAoc2VhKSBzcXVhcmUuIEZpbmFsbHksIGZvciBjb252ZW5pZW5jZSB5b3UgaGF2ZSBhbHNvIGRyYXduIHlvdXIgb3duIHBvc2l0aW9uLjxcL3A+XHJcblxyXG48cD5Ob3cgeW91IG11c3Qgc2V0IHVwIGEgXHVmYjAxeGVkIHJvdXRlIHRvIGdldCB0aGUgdHJlYXN1cmUuIFRoZSByb3V0ZSBtdXN0IHN0YXJ0IGF0IHlvdXIgcG9zaXRpb24sIGVuZCBhdCB0aGUgdHJlYXN1cmUsIGFuZCBjb25zaXN0IG9mIGEgc2VxdWVuY2Ugb2YgbW92ZXMuIEluIGVhY2ggbW92ZSwgeW91IGNhbiBnbyBvbmx5IHRvIGFuIChob3Jpem9udGFsbHkgb3IgdmVydGljYWxseSkgYWRqYWNlbnQgc3F1YXJlIHRoYXQgaXMgbm90IHBhcnQgb2YgYW4gaXNsYW5kLiBCdXQgYmV3YXJlOiBUaGUgVmlraW5nIHNoaXAgbWlnaHQgZm9sbG93IHlvdSwgdXNpbmcgdGhlIHNhbWUga2luZCBvZiBtb3ZlcyEgQWZ0ZXIgZWFjaCBvZiB5b3VyIG1vdmVzIGFjY29yZGluZyB0byB5b3VyIHJvdXRlLCB0aGUgVmlraW5nIHNoaXAgbWF5IG1vdmUgb3Igbm90LiBZb3VyIG1vdmUgYW5kIHRoZSBWaWtpbmdzJnJzcXVvOyByZWFjdGlvbiB0b2dldGhlciBpcyBjYWxsZWQgYSByb3VuZC48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgZXZlcnkgcm91bmQsIHRoZSBmb2xsb3dpbmcgY2hlY2tzIGFyZSBtYWRlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPklmIHlvdSBhcmUgaW4gbGluZSB3aXRoIHRoZSBWaWtpbmcgc2hpcCAoeW91IGFyZSBpbiB0aGUgc2FtZSB2ZXJ0aWNhbCBvciBob3Jpem9udGFsIGxpbmUgYXMgdGhlIFZpa2luZyBzaGlwIHdpdGggb25seSBzZWEgYmV0d2VlbiB0aGUgVmlraW5nIHNoaXAgYW5kIHlvdSksIHlvdSBhcmUgZGVhZC48XC9saT5cclxuXHQ8bGk+SWYgeW91IGFyZW4mcnNxdW87dCBkZWFkIGFuZCBhdCB0aGUgdHJlYXN1cmUtc3BvdCwgeW91IGdldCB0aGUgdHJlYXN1cmUuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZGVjaWRlcyB3aGV0aGVyIGl0IGlzIHBvc3NpYmxlIHRvIHNldCB1cCBhIFx1ZmIwMXhlZCByb3V0ZSBpbiBhZHZhbmNlIHN1Y2ggdGhhdCB5b3UgY2FuIGdldCB0aGUgdHJlYXN1cmUgYnkgZm9sbG93aW5nIHRoaXMgcm91dGUgYW5kIHdpbGwgbm90IGdldCBraWxsZWQgYnkgdGhlIFZpa2luZ3MgJm5kYXNoOyBubyBtYXR0ZXIgaG93IHRoZSBWaWtpbmcgc2hpcCBtb3Zlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgTSwgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIG1hcC4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbiBNIGNoYXJhY3RlcnMuIEVhY2ggY2hhcmFjdGVyIGRlc2NyaWJlcyBhIHNxdWFyZSBpbiB0aGUgbWFwLCBhbmQgaXMgZWl0aGVyIC4gKHNlYSksIEkgKHBhcnQgb2YgYW4gaXNsYW5kKSwgViAodGhlIFZpa2luZyBzaGlwKSwgWSAoeW91ciBwb3NpdGlvbiksIG9yIFQgKHRoZSB0cmVhc3VyZSkuIEVhY2ggb2YgViwgWSwgYW5kIFQgd2lsbCBvY2N1ciBleGFjdGx5IG9uY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IG11c3QgY29udGFpbiB0aGUgc3RyaW5nIFlFUywgaWYgaXQgaXMgcG9zc2libGUgdG8gc2V0IHVwIGEgcm91dGUgdG8gZ2V0IHRoZSB0cmVhc3VyZSwgb3IgTk8gb3RoZXJ3aXNlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZmlyc3QgZXhhbXBsZSwgdGhlIGZvbGxvd2luZyByb3V0ZSB3aWxsIGxldCB5b3UgZ2V0IHRoZSB0cmVhc3VyZTogRG93biwgRG93biwgRG93biwgUmlnaHQsIFJpZ2h0LCBSaWdodCwgRG93bi48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHNlY29uZCBhbmQgdGhpcmQgZXhhbXBsZXMsIHRoZXJlIGlzIG5vIHJvdXRlIHRvIHRoZSB0cmVhc3VyZSB0aGF0IHlvdSB3aWxsIHN1cnZpdmUuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOLCBNICZsZTsgNzAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 4번

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