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

문제

늑대 현우는 피에 굶주린 사냥꾼들에게 벗어나려고 도망치고 있다. 사냥꾼은 매우 똑똑해서 나무 뒤에 숨어있다. 현우도 이 사실을 알고있다. 하지만, 어떤 나무 뒤에 사냥꾼들이 숨어있는지 알지 못한다. 현우는 사냥꾼에게 잡히지 않기 위해서 숲의 한 오두막으로 대피하려고 한다. 현우는 나무와 거리가 최대한 떨어지는 경로로 대피하려고 한다.

숲은 N×M 크기의 그리드로 나타낼 수 있다. 각 칸이 빈 목초지라면 '.', 나무가 있다면 '+', 현재 현우의 위치는 'V', 오두막의 위치는 'J'로 나타나있다. 현우는 현재 있는 위치에서 동서남북으로 인접한 칸으로 이동할 수 있고, 나무가 있는 칸으로도 이동할 수 있다.

만약 현우가 지금 R행 C열에 있고, 나무가 A행 B열에 있다면, 현우와 나무의 거리는 |R-A| + |C-B|이다.

현우는 오두막으로 도망치는 가장 안전한 길로 이동하려고 한다. 가장 안전한 길이란 현우가 이동하는 모든 칸에서 나무와 거리의 최솟값이 가장 큰 경로이다. 또, 오두막이 있는 칸도 경로의 일부이기 때문에 나무와 거리를 계산해야 한다.

숲의 지도가 주어졌을 때, 가장 안전한 길을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M (1 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개 줄에는 숲의 지도가 주어진다. 지도에 'V'와 'J'는 딱 하나만 있고, 적어도 하나의 '+'가 있다.

출력

첫째 줄에 가장 안전한 경로에서 나무와 현우와 거리의 최솟값을 출력한다.

예제 입력 1

4 4
+...
....
....
V..J

예제 출력 1

3

예제 입력 2

4 5
.....
.+++.
.+.+.
V+.J+

예제 출력 2

0
W3sicHJvYmxlbV9pZCI6IjI5MTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyOTFcdWIzMDAgXHVjMGFjXHViMGU1XHVhZmJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyOTFcdWIzMDAgXHVkNjA0XHVjNmIwXHViMjk0IFx1ZDUzY1x1YzVkMCBcdWFkNzZcdWM4ZmNcdWI5YjAgXHVjMGFjXHViMGU1XHVhZmJjXHViNGU0XHVjNWQwXHVhYzhjIFx1YmM5N1x1YzViNFx1YjA5OFx1YjgyNFx1YWNlMCBcdWIzYzRcdWI5ZGRcdWNlNThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYWNcdWIwZTVcdWFmYmNcdWM3NDAgXHViOWU0XHVjNmIwIFx1YjYxMVx1YjYxMVx1ZDU3NFx1YzExYyBcdWIwOThcdWJiMzQgXHViNGE0XHVjNWQwIFx1YzIyOFx1YzViNFx1Yzc4OFx1YjJlNC4gXHVkNjA0XHVjNmIwXHViM2M0IFx1Yzc3NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHVjNTRjXHVhY2UwXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YzViNFx1YjVhNCBcdWIwOThcdWJiMzQgXHViNGE0XHVjNWQwIFx1YzBhY1x1YjBlNVx1YWZiY1x1YjRlNFx1Yzc3NCBcdWMyMjhcdWM1YjRcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNTRjXHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC4gXHVkNjA0XHVjNmIwXHViMjk0IFx1YzBhY1x1YjBlNVx1YWZiY1x1YzVkMFx1YWM4YyBcdWM3YTFcdWQ3ODhcdWM5YzAgXHVjNTRhXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWMyMzJcdWM3NTggXHVkNTVjIFx1YzYyNFx1YjQ1MFx1YjljOVx1YzczY1x1Yjg1YyBcdWIzMDBcdWQ1M2NcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ2MDRcdWM2YjBcdWIyOTQgXHViMDk4XHViYjM0XHVjNjQwIFx1YWM3MFx1YjlhY1x1YWMwMCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjg1YyBcdWIzMDBcdWQ1M2NcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMzJcdWM3NDAgTiZ0aW1lcztNIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFkZjhcdWI5YWNcdWI0ZGNcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWNlNzhcdWM3NzQgXHViZTQ4IFx1YmFhOVx1Y2QwOFx1YzljMFx1Yjc3Y1x1YmE3NCAmIzM5Oy4mIzM5OywgXHViMDk4XHViYjM0XHVhYzAwIFx1Yzc4OFx1YjJlNFx1YmE3NCAmIzM5OysmIzM5OywgXHVkNjA0XHVjN2FjIFx1ZDYwNFx1YzZiMFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgJiMzOTtWJiMzOTssIFx1YzYyNFx1YjQ1MFx1YjljOVx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgJiMzOTtKJiMzOTtcdWI4NWMgXHViMDk4XHVkMGMwXHViMDk4XHVjNzg4XHViMmU0LiBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNThcdWM1ZDBcdWMxMWMgXHViM2Q5XHVjMTFjXHViMGE4XHViZDgxXHVjNzNjXHViODVjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzNjXHViODVjXHViM2M0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHVkNjA0XHVjNmIwXHVhYzAwIFx1YzljMFx1YWUwOCBSXHVkNTg5IENcdWM1ZjRcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWIwOThcdWJiMzRcdWFjMDAgQVx1ZDU4OSBCXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVkNjA0XHVjNmIwXHVjNjQwIFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgfFItQXwgKyB8Qy1CfFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjNmIwXHViMjk0IFx1YzYyNFx1YjQ1MFx1YjljOVx1YzczY1x1Yjg1YyBcdWIzYzRcdWI5ZGRcdWNlNThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzU0OFx1YzgwNFx1ZDU1YyBcdWFlMzhcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YzU0OFx1YzgwNFx1ZDU1YyBcdWFlMzhcdWM3NzRcdWI3ODAgXHVkNjA0XHVjNmIwXHVhYzAwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YjA5OFx1YmIzNFx1YzY0MCBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzc0IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhY2JkXHViODVjXHVjNzc0XHViMmU0LiBcdWI2MTAsIFx1YzYyNFx1YjQ1MFx1YjljOVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHViM2M0IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWM3N2NcdWJkODBcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YjA5OFx1YmIzNFx1YzY0MCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjMyXHVjNzU4IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVjNTQ4XHVjODA0XHVkNTVjIFx1YWUzOFx1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNICgxICZsZTsgTiwgTSAmbGU7IDUwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIzMlx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5YzBcdWIzYzRcdWM1ZDAgJiMzOTtWJiMzOTtcdWM2NDAgJiMzOTtKJiMzOTtcdWIyOTQgXHViNTMxIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWM3ODhcdWFjZTAsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWM3NTggJiMzOTsrJiMzOTtcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YzU0OFx1YzgwNFx1ZDU1YyBcdWFjYmRcdWI4NWNcdWM1ZDBcdWMxMWMgXHViMDk4XHViYjM0XHVjNjQwIFx1ZDYwNFx1YzZiMFx1YzY0MCBcdWFjNzBcdWI5YWNcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTE3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVlVLIiwiZGVzY3JpcHRpb24iOiI8cD5WamVrb3NsYXYgdGhlIFdvbGYgaXMgcnVubmluZyBhd2F5IGZyb20gYSBidW5jaCBvZiBibG9vZCBodW5ncnkgaHVudGVycy4gVGhlIGh1bnRlcnMgYXJlIHNtYXJ0IGFuZCBoaWRlIGJlaGluZCB0cmVlcy4gVmpla29zbGF2IGtub3dzIHRoaXMsIGJ1dCBkb2VzbiYjMzk7dCBrbm93IHdoaWNoIHRyZWVzLiBIZSB3b3VsZCBsaWtlIHRvIHJ1biB0byBoaXMgY29tZm9ydGFibGUsIGNpdmlsaXplZCBjb3R0YWdlIChhcyBvcHBvc2VkIHRvIHRoZSBodW50ZXJzIHF1aXRlIHVuY2l2aWxpemVkIGRlbiwgeWVzIEkgYW0gcm9vdGluZyBmb3IgdGhlIFdvbGYgaGVyZSkgc3RheWluZyBhcyBmYXIgYXdheSBhcyBwb3NzaWJsZSBmcm9tIGFueSB0cmVlcy48XC9wPlxyXG5cclxuPHA+VGhlIGZvcmVzdCBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBOIGJ5IE0gZ2lyZC4gTGV0IHVzIG1hcmsgZW1wdHkgbWVhZG93IHBhdGNoZXMgd2l0aCAmIzM5Oy4mIzM5OywgcGF0Y2hlcyB3aXRoIGEgdHJlZSBpbiB0aGUgbWlkZGxlIHdpdGggJiMzOTsrJiMzOTssIFZqZWtvc2xhdiYjMzk7cyBjdXJyZW50IHBvc2l0aW9uIHdpdGggJiMzOTtWJiMzOTsgYW5kIHRoZSBwb3NpdGlvbiBvZiBoaXMgY290dGFnZSB3aXRoICYjMzk7SiYjMzk7LiBWamVrb3NsYXYgY2FuIHJ1biBmcm9tIGhpcyBjdXJyZW50IHBhdGNoIHRvIGFueSBvdGhlciBwYXRjaCBub3J0aCwgZWFzdCwgc291dGggb3Igd2VzdCBmcm9tIGhpbSwgZXZlbiBpZiBpdCBjb250YWlucyBhIHRyZWUuPFwvcD5cclxuXHJcbjxwPklmIFZqZWtvc2xhdiBpcyBzdGFuZGluZyBpbiBSLXRoIHJvdyBhbmQgQy10aCBjb2x1bW4gb24gdGhlIGdyaWQgYW5kIHRoZXJlIGlzIGEgdHJlZSBpbiB0aGUgQS10aCByb3cgYW5kIEItdGggY29sdW1uIHRoZW4gdGhlIGRpc3RhbmNlIGJldHdlZW4gVmpla29zbGF2IGFuZCB0aGF0IHRyZWUgaXM6PFwvcD5cclxuXHJcbjxwPnxSLUF8ICsgfEMtQnw8XC9wPlxyXG5cclxuPHA+SGVscCBWamVrb3NsYXYgZmluZCB0aGUgYmVzdCByb3V0ZSB0byBoaXMgY290dGFnZS4gVGhlIGJlc3Qgcm91dGUgaXMgYW55IHJvdXRlIHRoYXQgbWF4aW1pemVzIHRoZSBtaW5pbWFsIGRpc3RhbmNlIGJldHdlZW4gVmpla29zbGF2IGFuZCBhbGwgdHJlZXMgYXQgYW55IGdpdmVuIG1vbWVudC48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IFZqZWtvc2xhdiYjMzk7cyBjb3R0YWdlIGRvZXNuJiMzOTt0IG9jY3VweSB0aGUgZW50aXJlIHBhdGNoIHNvIHRoYXQgcGF0Y2ggbXVzdCBhbHNvIGJlIGluY2x1ZGVkIGluIHRoZSByb3V0ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4gYW5kIE0gKDEgJmxlOyBOLCBNICZsZTsgNTAwKSwgZ3JpZCBkaW1lbnNpb25zLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW4gTSBjaGFyYWN0ZXJzIGVhY2g6ICYjMzk7LiYjMzk7LCAmIzM5OysmIzM5OywgJiMzOTtWJiMzOTssICYjMzk7SiYjMzk7LjxcL3A+XHJcblxyXG48cD5JbnB1dCB3aWxsIGNvbnRhaW4gZXhhY3RseSBvbmUgY2hhcmFjdGVyICYjMzk7ViYjMzk7IGFuZCAmIzM5O0omIzM5OyBhbmQgYXQgbGVhc3Qgb25lIGNoYXJhY3RlciAmIzM5OysmIzM5Oy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzaW5nbGUgaW50ZWdlciwgdGhlIG1pbmltYWwgZGlzdGFuY2UgZnJvbSBhIHRyZWUgaW4gdGhlIG9wdGltYWwgcm91dGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #2 4번