시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB6040151699623.669%

문제

n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다.

이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(2 ≤ n ≤ 100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다.

출력

첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다.

예제 입력 1

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjE5ODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNzc0XHViM2Q5IiwiZGVzY3JpcHRpb24iOiI8cD5uJnRpbWVzO25cdWM5ZGNcdWI5YWNcdWM3NTggXHViYzMwXHVjNWY0XHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJjMzBcdWM1ZjRcdWM3NTggKDEsIDEpXHVjNWQwXHVjMTFjIChuLCBuKVx1YWU0Y1x1YzljMCBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWIzZDlcdWQ1NjAgXHViNTRjXHViMjk0IFx1YzBjMSwgXHVkNTU4LCBcdWM4OGMsIFx1YzZiMFx1Yzc1OCBcdWIxMjQgXHVjNzc4XHVjODExXHVkNTVjIFx1Y2U3OFx1YzczY1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyZTQgXHViY2Y0XHViYTc0LCBcdWJjMzBcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVhYzcwXHVjY2QwXHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzcwXHVjY2QwIFx1YWMwNCBcdWMyMThcdWI0ZTQgXHVjOTExIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1YWNmYyBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM1NDRcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuKDIgJmxlOyBuICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjMzBcdWM1ZjRcdWM3NTggXHVhYzAxIFx1YzIxOFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDIwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIChcdWNkNWNcdWIzMDAgLSBcdWNkNWNcdWMxOGMpXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM1NDRcdWM5YzggXHViNTRjXHVjNzU4IFx1YWRmOCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE5ODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIb25leW1vb24gSGlrZSIsImRlc2NyaXB0aW9uIjoiPHA+RW1tYSBpcyBvbiBhIGhpa2luZyB0cmlwIHdpdGggRXJpYywgaGVyIGZyZXNobHktbWFycmllZCBodXNiYW5kLCBmb3IgdGhlaXIgaG9uZXltb29uLiBUaGV5IGFyZSBoaWtpbmcgZnJvbSBvbmUgY2FiaW4gdG8gdGhlIG5leHQgZXZlcnkgZGF5LiBVbmZvcnR1bmF0ZWx5LCBFcmljIGlzIG5vdCBhcyBcdWZiMDF0IGFzIEVtbWEgYW5kIGlzIHNsb3dseSBnZXR0aW5nIHRpcmVkLiBTaW5jZSBFbW1hIGRvZXMgbm90IHdhbnQgdG8gc3RhcnQgdGhlaXIgbmV3bHktZm9ybWVkIG1hcnJpYWdlIHdpdGggYSBzZXJpb3VzIGNvblx1ZmIwMmljdCAoYW5kIG5lZWRzIHNvbWVib2R5IHRvIGtlZXAgaGVyIHdhcm0gaW4gdGhlIG5pZ2h0cyksIHNoZSBkZWNpZGVzIHRvIHBsYW4gdGhlIG5leHQgZGF5IHRyaXBzIHNvIHRoYXQgdGhleSBhcmUgbm90IHNvIHN0cmVudW91cyBmb3IgRXJpYy48XC9wPlxyXG5cclxuPHA+SW4gdGhlIHBhc3QgZGF5cywgRW1tYSBoYXMgZGlzY292ZXJlZCBhIHN1cnByaXNpbmcgZmFjdCBhYm91dCBoZXIgaHVzYmFuZC4gSGUgaXMgbm90IHNvIG11Y2ggdGlyZWQgYnkgdGhlIGxlbmd0aCBvZiB0aGVpciBkYWlseSB0cmlwIG9yIHRoZSB0b3RhbCBhbW91bnQgb2YgbWV0ZXJzIHRoZXkgaGFkIHRvIGNsaW1iLiBJbnN0ZWFkLCBFcmljIGlzIHRpcmVkIHRoZSBtb3JlLCB0aGUgYmlnZ2VyIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGhpZ2hlc3QgYW5kIHRoZSBsb3dlc3QgcG9pbnQgb2YgdG9kYXkmcnNxdW87cyByb3V0ZSBiZWNvbWVzLiBFbW1hIGFzc3VtZXMgdGhpcyBpcyBkdWUgdG8gcHN5Y2hvbG9naWNhbCBmYWN0b3JzLiBJdCBqdXN0IHNvdW5kcyBhIGxvdCBtb3JlIGRpZlx1ZmIwMWN1bHQgdG8gY2xpbWIgb25jZSBmcm9tIDUwMCBtZXRlciB0byAxLDUwMCBtZXRlcnMgdGhhbiB0byBjbGltYiBmcm9tIDIwMCB0byA0MDAgbWV0ZXJzIHRlbiB0aW1lcywgYWx0aG91Z2ggeW91IGNsaW1iZWQgdHdpY2UgYXMgbXVjaCBpbiB0aGUgbGF0dGVyIGNhc2UuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGFuIGFsdGl0dWRlIG1hcCBvZiB0aGUgdGVycmFpbiwgeW91IHNob3VsZCBoZWxwIEVtbWEgaW4gXHVmYjAxbmRpbmcgYSBwYXRoIHRoYXQgbWluaW1pemVzIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gaXRzIGhpZ2hlc3QgYW5kIGl0cyBsb3dlc3QgZWxldmF0aW9uLCBzbyB0aGF0IEVyaWMgZG9lcyBub3QgZmVlbCBhcyB0aXJlZC4gVGhlIGNhYmluIHRoZXkgc3RhcnQgYXQgaXMgbG9jYXRlZCBhdCB0aGUgdG9wLWxlZnQgY29ybmVyIGFuZCB0aGVpciBkZXN0aW5hdGlvbiBpcyB0aGUgYm90dG9tLXJpZ2h0IGNvcm5lciBvZiB0aGUgbWFwLiBUaGV5IGNhbiBtb3ZlIGFsb25nIGFueSBvZiB0aGUgZm91ciBtYWpvciBkaXJlY3Rpb25zIGJ1dCBub3Qgb24gYSBkaWFnb25hbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIHNjZW5hcmlvcy4gRWFjaCBzY2VuYXJpbyBzdGFydHMgd2l0aCBhIG51bWJlciBuICgyICZsZTsgbiAmbGU7IDEwMCksIHRoZSBzaXplIG9mIHRoZSBhcmVhLiBUaGUgZWxldmF0aW9ucyBvZiB0aGUgdGVycmFpbiBhcmUgZ2l2ZW4gYXMgYSBuICZ0aW1lczsgbiBpbnRlZ2VyIG1hdHJpeCAoaDxzdWI+aSxqPFwvc3ViPikgKDAgJmxlOyBoPHN1Yj5pLGo8XC9zdWI+ICZsZTsgMjAwKSBvbiBuIGxpbmVzLCB3aGVyZSBlYWNoIGxpbmUgY29udGFpbnMgbiBzcGFjZS1zZXBhcmF0ZWQgZWxldmF0aW9ucy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZvciBldmVyeSBzY2VuYXJpbyBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyAmbGRxdW87U2NlbmFyaW8gI2k6JnJkcXVvOywgd2hlcmUgaSBpcyB0aGUgbnVtYmVyIG9mIHRoZSBzY2VuYXJpbyBzdGFydGluZyBhdCAxLiBUaGVuLCBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgaGlnaGVzdCBhbmQgdGhlIGxvd2VzdCBlbGV2YXRpb24gb24gdGhlIG9wdGltYWwgcGF0aC4gVGVybWluYXRlIHRoZSBvdXRwdXQgZm9yIHRoZSBzY2VuYXJpbyB3aXRoIGEgYmxhbmsgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2006 6번