시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 3056 710 354 19.334%

문제

상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.

매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.

상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장 작은 피로도로 모든 집에 배달을 하려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)

다음 N개 줄에는 마을을 나타내는 행렬이 주어진다. 'P'는 한 번만 주어지며, 'K'는 적어도 한 번 주어진다.

다음 N개 줄에는 행렬로 나뉘어진 지역의 고도가 행렬 형태로 주어진다. 고도는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 가장 작은 피로도를 출력한다.

예제 입력 1

3
K.P
...
K.K
3 3 4
9 5 9
8 3 7

예제 출력 1

5

예제 입력 2

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

예제 출력 2

2

예제 입력 3

2
P.
.K
2 1
3 2

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjI4NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5ZDFcdWJjMzBcdWM2ZDAgXHVkNTVjXHVjMGMxXHViMzU1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHVjNWI4XHViMzU1IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzZiMFx1Y2NiNFx1YWQ2ZFx1YzVkMCBcdWM5YzFcdWM1YzVcdWM3NDQgXHVjNWJiXHVjNWM4XHViMmU0LiBcdWI5YzhcdWM3NDRcdWM3NDAgTiZ0aW1lcztOIFx1ZDU4OVx1YjgyY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTg5XHViODJjXHViODVjIFx1YjA5OFx1YjI1OFx1YzViNFx1YzljNCBcdWFjMDEgXHVjOWMwXHVjNWVkXHVjNzQwIFx1YzZiMFx1Y2NiNFx1YWQ2ZFx1Yzc0MCAmIzM5O1AmIzM5OywgXHVjOWQxXHVjNzQwICYjMzk7SyYjMzk7LCBcdWJhYTlcdWNkMDhcdWM5YzBcdWIyOTQgJiMzOTsuJiMzOTsgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwLCBcdWFjMDEgXHVjOWMwXHVjNWVkXHVjNzU4IFx1YWNlMFx1YjNjNFx1YjNjNCBcdWM1NGNcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5ZTRcdWM3N2MgXHVjNTQ0XHVjZTY4IFx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NTggXHViYWE4XHViNGUwIFx1YzlkMVx1YzVkMCBcdWM2YjBcdWQzYjhcdWM3NDQgXHViYzMwXHViMmVjXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViYzMwXHViMmVjXHVjNzQwIFx1YjljOFx1Yzc0NFx1YzVkMCBcdWQ1NThcdWIwOThcdWJjMTZcdWM1ZDAgXHVjNWM2XHViMjk0IFx1YzZiMFx1Y2NiNFx1YWQ2ZCAmIzM5O1AmIzM5O1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjMGMxXHViMzU1XHVjNzc0XHViMjk0IFx1ZDYwNFx1YzdhYyBcdWM3ODhcdWIyOTQgXHVjZTc4XHVhY2ZjIFx1YzIxOFx1ZDNjOSwgXHVjMjE4XHVjOWMxLCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5IFx1ZDNiOFx1YzljMFx1Yjk3YyBcdWJjMzBcdWIyZWNcdWQ1NThcdWFjZTAgXHViMDljIFx1Yzc3NFx1ZDZjNFx1YzVkMFx1YjI5NCBcdWIyZTRcdWMyZGMgXHVjNmIwXHVjY2I0XHVhZDZkXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzY0MFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWM3NzRcdWI4MDdcdWFjOGMgXHViOWU0XHVjNzdjIFx1YzU0NFx1Y2U2OCBcdWJjMzBcdWIyZWNcdWM3NDQgXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWM1YmNcdWI5YzhcdWIwOTggXHVkNzk4XHViNGUwXHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gXHVjMGMxXHViMzU1XHVjNzc0XHVhYzAwIFx1YmMzMFx1YjJlY1x1ZDU1OFx1YmE3NFx1YzExYyBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVjZTc4IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YWNmM1x1YWNmYyBcdWIwYWVcdWM3NDAgXHVhY2YzXHVjNzU4IFx1YWNlMFx1YjNjNCBcdWNjMjhcdWM3NzRcdWI5N2MgXHVkNTNjXHViODVjXHViM2M0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1ZDUzY1x1Yjg1Y1x1YjNjNFx1Yjg1YyBcdWJhYThcdWI0ZTAgXHVjOWQxXHVjNWQwIFx1YmMzMFx1YjJlY1x1Yzc0NCBcdWQ1NThcdWI4MjRcdWJhNzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyA1MCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVkNTg5XHViODJjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTtQJiMzOTtcdWIyOTQgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsICYjMzk7SyYjMzk7XHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViYzg4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1YjgyY1x1Yjg1YyBcdWIwOThcdWIyNThcdWM1YjRcdWM5YzQgXHVjOWMwXHVjNWVkXHVjNzU4IFx1YWNlMFx1YjNjNFx1YWMwMCBcdWQ1ODlcdWI4MmMgXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhY2UwXHViM2M0XHViMjk0IDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVkNTNjXHViODVjXHViM2M0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUE9cdTAxNjBUQVIiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyBnb3QgYSBtYWlsbWFuIGpvYiBpbiBhIHNtYWxsIHRvd24gaW4gdGhlIGhpbGxzLiBUaGUgdG93biBjYW4gYmUgcmVwcmVzZW50ZWQgYnkgYSBOJnRpbWVzO04gbWF0cml4LiBFYWNoIGZpZWxkIGNvbnRhaW5zIG9uZSBvZiB0aGUgZm9sbG93aW5nLCBleGNsdXNpdmVseTogYSBob3VzZSBkZW5vdGVkIGJ5ICZsc3F1bztLJnJzcXVvOywgdGhlIHBvc3Qgb2ZmaWNlIGRlbm90ZWQgYnkgJmxzcXVvO1AmcnNxdW87LCBvciBhIHBhc3R1cmUgZGVub3RlZCBieSAmbHNxdW87LiZyc3F1bzsuIEFkZGl0aW9uYWxseSwgZWFjaCBmaWVsZCBpcyBhc3NpZ25lZCBhbiBhbHRpdHVkZS48XC9wPlxyXG5cclxuPHA+RXZlcnkgbW9ybmluZywgTWlya28gZGVsaXZlcnMgbWFpbCB0byBhbGwgaG91c2VzIGluIHRoZSB0b3duLiBIZSBzdGFydHMgYXQgdGhlIGZpZWxkIGRlbm90ZWQgYnkgJmxzcXVvO1AmcnNxdW87LCB3aGljaCByZXByZXNlbnRzIGEgc2luZ2xlIHBvc3Qgb2ZmaWNlIGluIHRoZSB0b3duLiBNaXJrbyBpcyBhbGxvd2VkIHRvIG1vdmUgaG9yaXpvbnRhbGx5LCB2ZXJ0aWNhbGx5IGFuZCBkaWFnb25hbGx5LCB0byBhZGphY2VudCBzcXVhcmVzIG9ubHkuIE9uY2UgaGUgZGVsaXZlcnMgdGhlIGxhc3QgcGllY2Ugb2YgbWFpbCwgaGUgbXVzdCByZXR1cm4gdG8gdGhlIHBvc3Qgb2ZmaWNlLjxcL3A+XHJcblxyXG48cD5NaXJrbyBkaWQgbm90IGhhdmUgYSBjbHVlIGFib3V0IGhvdyB0aXJlc29tZSBoaXMgam9iIHdpbGwgYmUuIExldCB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBoZWlnaHRzIG9mIHRoZSBoaWdoZXN0IGFuZCB0aGUgbG93ZXN0IGZpZWxkIE1pcmtvIHZpc2l0cyB3aGlsZSBkZWxpdmVyaW5nIHRoZSBtYWlsIGJlIGVxdWFsIHRvIGhpcyB0aXJlZG5lc3MuIEhlbHAgaGltIG91dCBhbmQgZGV0ZXJtaW5lIHRoZSBsZWFzdCB0aXJlZG5lc3MgcG9zc2libGUgZm9yIE1pcmtvIHRvIGRlbGl2ZXIgYWxsIHRoZSBtYWlsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDUwKS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBOIGxpbmVzIHJlcHJlc2VudCBmaWVsZHMgaW4gdGhlIGNvcnJlc3BvbmRpbmcgbWF0cml4IHJvdy4gVGhlIGNoYXJhY3RlciAmbHNxdW87UCZyc3F1bzsgd2lsbCBhcHBlYXIgZXhhY3RseSBvbmNlLCB3aGlsZSB0aGUgY2hhcmFjdGVyICZsc3F1bztLJnJzcXVvOyB3aWxsIGFwcGVhciBhdCBsZWFzdCBvbmNlLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgZWFjaCBjb250YWluIE4gcG9zaXRpdmUgaW50ZWdlcnMsIHRoZSBhbHRpdHVkZXMgb2YgdGhlIGZpZWxkcyBpbiB0aGUgY29ycmVzcG9uZGluZyBtYXRyaXggcm93LiBUaG9zZSB2YWx1ZXMgYXJlIGxlc3MgdGhhbiAxIDAwMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gYSBzaW5nbGUgbGluZSBvZiBvdXRwdXQgcHJpbnQgYSBzaW5nbGUgaW50ZWdlciB0aGF0IHJlcHJlc2VudHMgdGhlIG1pbmltdW0gcG9zc2libGUgdGlyZWRuZXNzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 4번