시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 284 88 60 29.412%

문제

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

숲은 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
W3sicHJvYmxlbV9pZCI6IjI5MTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyOTFcdWIzMDAgXHVjMGFjXHViMGU1XHVhZmJjIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0XHViMjkxXHViMzAwIFx1ZDYwNFx1YzZiMFx1YjI5NCBcdWQ1M2NcdWM1ZDAgXHVhZDc2XHVjOGZjXHViOWIwIFx1YzBhY1x1YjBlNVx1YWZiY1x1YjRlNFx1YzVkMFx1YWM4YyBcdWJjOTdcdWM1YjRcdWIwOThcdWI4MjRcdWFjZTAgXHViM2M0XHViOWRkXHVjZTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMGFjXHViMGU1XHVhZmJjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWI2MTFcdWI2MTFcdWQ1NzRcdWMxMWMgXHViMDk4XHViYjM0IFx1YjRhNFx1YzVkMCBcdWMyMjhcdWM1YjRcdWM3ODhcdWIyZTQuIFx1ZDYwNFx1YzZiMFx1YjNjNCBcdWM3NzQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWNlMFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM1YjRcdWI1YTQgXHViMDk4XHViYjM0IFx1YjRhNFx1YzVkMCBcdWMwYWNcdWIwZTVcdWFmYmNcdWI0ZTRcdWM3NzQgXHVjMjI4XHVjNWI0XHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuIFx1ZDYwNFx1YzZiMFx1YjI5NCBcdWMwYWNcdWIwZTVcdWFmYmNcdWM1ZDBcdWFjOGMgXHVjN2ExXHVkNzg4XHVjOWMwIFx1YzU0YVx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjMjMyXHVjNzU4IFx1ZDU1YyBcdWM2MjRcdWI0NTBcdWI5YzlcdWM3M2NcdWI4NWMgXHViMzAwXHVkNTNjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVkNjA0XHVjNmIwXHViMjk0IFx1YjA5OFx1YmIzNFx1YzY0MCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVjZDVjXHViMzAwXHVkNTVjIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWI4NWMgXHViMzAwXHVkNTNjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMjMyXHVjNzQwIE4mdGltZXM7TSBcdWQwNmNcdWFlMzBcdWM3NTggXHVhZGY4XHViOWFjXHViNGRjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZTc4XHVjNzc0IFx1YmU0OCBcdWJhYTlcdWNkMDhcdWM5YzBcdWI3N2NcdWJhNzQgJiMzOTsuJiMzOTssIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgJiMzOTsrJiMzOTssIFx1ZDYwNFx1YzdhYyBcdWQ2MDRcdWM2YjBcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0ICYjMzk7ViYjMzk7LCBcdWM2MjRcdWI0NTBcdWI5YzlcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0ICYjMzk7SiYjMzk7XHViODVjIFx1YjA5OFx1ZDBjMFx1YjA5OFx1Yzc4OFx1YjJlNC4gXHVkNjA0XHVjNmIwXHViMjk0IFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YjNkOVx1YzExY1x1YjBhOFx1YmQ4MVx1YzczY1x1Yjg1YyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWIwOThcdWJiMzRcdWFjMDAgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YzczY1x1Yjg1Y1x1YjNjNCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViOWNjXHVjNTdkIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWM5YzBcdWFlMDggUlx1ZDU4OSBDXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHViMDk4XHViYjM0XHVhYzAwIEFcdWQ1ODkgQlx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1ZDYwNFx1YzZiMFx1YzY0MCBcdWIwOThcdWJiMzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IHxSLUF8ICsgfEMtQnxcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDYwNFx1YzZiMFx1YjI5NCBcdWM2MjRcdWI0NTBcdWI5YzlcdWM3M2NcdWI4NWMgXHViM2M0XHViOWRkXHVjZTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM1NDhcdWM4MDRcdWQ1NWMgXHVhZTM4XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWM1NDhcdWM4MDRcdWQ1NWMgXHVhZTM4XHVjNzc0XHViNzgwIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIFx1Y2U3OFx1YzVkMFx1YzExYyBcdWIwOThcdWJiMzRcdWM2NDAgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWNiZFx1Yjg1Y1x1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWM2MjRcdWI0NTBcdWI5YzlcdWM3NzQgXHVjNzg4XHViMjk0IFx1Y2U3OFx1YjNjNCBcdWFjYmRcdWI4NWNcdWM3NTggXHVjNzdjXHViZDgwXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIwOThcdWJiMzRcdWM2NDAgXHVhYzcwXHViOWFjXHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzIzMlx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YzU0OFx1YzgwNFx1ZDU1YyBcdWFlMzhcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgTSAoMSAmbGU7IE4sIE0gJmxlOyA1MDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMzJcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOWMwXHViM2M0XHVjNWQwICYjMzk7ViYjMzk7XHVjNjQwICYjMzk7SiYjMzk7XHViMjk0IFx1YjUzMSBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjNzg4XHVhY2UwLCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHVjNzU4ICYjMzk7KyYjMzk7XHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM1NDhcdWM4MDRcdWQ1NWMgXHVhY2JkXHViODVjXHVjNWQwXHVjMTFjIFx1YjA5OFx1YmIzNFx1YzY0MCBcdWQ2MDRcdWM2YjBcdWM2NDAgXHVhYzcwXHViOWFjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkxNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlZVSyIsImRlc2NyaXB0aW9uIjoiPHA+Vmpla29zbGF2IHRoZSBXb2xmIGlzIHJ1bm5pbmcgYXdheSBmcm9tIGEgYnVuY2ggb2YgYmxvb2QgaHVuZ3J5IGh1bnRlcnMuIFRoZSBodW50ZXJzIGFyZSBzbWFydCBhbmQgaGlkZSBiZWhpbmQgdHJlZXMuIFZqZWtvc2xhdiBrbm93cyB0aGlzLCBidXQgZG9lc24mIzM5O3Qga25vdyB3aGljaCB0cmVlcy4gSGUgd291bGQgbGlrZSB0byBydW4gdG8gaGlzIGNvbWZvcnRhYmxlLCBjaXZpbGl6ZWQgY290dGFnZSAoYXMgb3Bwb3NlZCB0byB0aGUgaHVudGVycyBxdWl0ZSB1bmNpdmlsaXplZCBkZW4sIHllcyBJIGFtIHJvb3RpbmcgZm9yIHRoZSBXb2xmIGhlcmUpIHN0YXlpbmcgYXMgZmFyIGF3YXkgYXMgcG9zc2libGUgZnJvbSBhbnkgdHJlZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBmb3Jlc3QgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgTiBieSBNIGdpcmQuIExldCB1cyBtYXJrIGVtcHR5IG1lYWRvdyBwYXRjaGVzIHdpdGggJiMzOTsuJiMzOTssIHBhdGNoZXMgd2l0aCBhIHRyZWUgaW4gdGhlIG1pZGRsZSB3aXRoICYjMzk7KyYjMzk7LCBWamVrb3NsYXYmIzM5O3MgY3VycmVudCBwb3NpdGlvbiB3aXRoICYjMzk7ViYjMzk7IGFuZCB0aGUgcG9zaXRpb24gb2YgaGlzIGNvdHRhZ2Ugd2l0aCAmIzM5O0omIzM5Oy4gVmpla29zbGF2IGNhbiBydW4gZnJvbSBoaXMgY3VycmVudCBwYXRjaCB0byBhbnkgb3RoZXIgcGF0Y2ggbm9ydGgsIGVhc3QsIHNvdXRoIG9yIHdlc3QgZnJvbSBoaW0sIGV2ZW4gaWYgaXQgY29udGFpbnMgYSB0cmVlLjxcL3A+XHJcblxyXG48cD5JZiBWamVrb3NsYXYgaXMgc3RhbmRpbmcgaW4gUi10aCByb3cgYW5kIEMtdGggY29sdW1uIG9uIHRoZSBncmlkIGFuZCB0aGVyZSBpcyBhIHRyZWUgaW4gdGhlIEEtdGggcm93IGFuZCBCLXRoIGNvbHVtbiB0aGVuIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIFZqZWtvc2xhdiBhbmQgdGhhdCB0cmVlIGlzOjxcL3A+XHJcblxyXG48cD58Ui1BfCArIHxDLUJ8PFwvcD5cclxuXHJcbjxwPkhlbHAgVmpla29zbGF2IGZpbmQgdGhlIGJlc3Qgcm91dGUgdG8gaGlzIGNvdHRhZ2UuIFRoZSBiZXN0IHJvdXRlIGlzIGFueSByb3V0ZSB0aGF0IG1heGltaXplcyB0aGUgbWluaW1hbCBkaXN0YW5jZSBiZXR3ZWVuIFZqZWtvc2xhdiBhbmQgYWxsIHRyZWVzIGF0IGFueSBnaXZlbiBtb21lbnQuPFwvcD5cclxuXHJcbjxwPk5vdGUgdGhhdCBWamVrb3NsYXYmIzM5O3MgY290dGFnZSBkb2VzbiYjMzk7dCBvY2N1cHkgdGhlIGVudGlyZSBwYXRjaCBzbyB0aGF0IHBhdGNoIG11c3QgYWxzbyBiZSBpbmNsdWRlZCBpbiB0aGUgcm91dGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBOIGFuZCBNICgxICZsZTsgTiwgTSAmbGU7IDUwMCksIGdyaWQgZGltZW5zaW9ucy48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBjb250YWluIE0gY2hhcmFjdGVycyBlYWNoOiAmIzM5Oy4mIzM5OywgJiMzOTsrJiMzOTssICYjMzk7ViYjMzk7LCAmIzM5O0omIzM5Oy48XC9wPlxyXG5cclxuPHA+SW5wdXQgd2lsbCBjb250YWluIGV4YWN0bHkgb25lIGNoYXJhY3RlciAmIzM5O1YmIzM5OyBhbmQgJiMzOTtKJiMzOTsgYW5kIGF0IGxlYXN0IG9uZSBjaGFyYWN0ZXIgJiMzOTsrJiMzOTsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc2luZ2xlIGludGVnZXIsIHRoZSBtaW5pbWFsIGRpc3RhbmNlIGZyb20gYSB0cmVlIGluIHRoZSBvcHRpbWFsIHJvdXRlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==