시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB94235929241.595%

문제

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.

산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.) 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.

문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

입력

첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 산봉우리의 개수를 출력한다.

예제 입력 1

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjEyNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxOGRcdWM3YTUgXHVhZDAwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHViYmZjXHVjMmRkXHVjNzc0XHVhYzAwIFx1YWQwMFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWIxOGRcdWM3YTVcdWM3NDAgTiZ0aW1lcztNIFx1YWNhOVx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJiZmNcdWMyZGRcdWM3NzRcdWIyOTQgXHViMThkXHVjN2E1XHVjNzQ0IFx1YWQwMFx1YjlhY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMGIwXHViZDA5XHVjNmIwXHViOWFjXHViOWM4XHViMmU0IFx1YWNiZFx1YmU0NFx1YzZkMFx1Yjk3YyBcdWJjMzBcdWNlNThcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0IFx1YjE4ZFx1YzdhNVx1YzVkMCBcdWMwYjBcdWJkMDlcdWM2YjBcdWI5YWNcdWFjMDAgXHVjZDFkIFx1YmE4NyBcdWFjMWMgXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1YzEzOFx1YjI5NCBcdWFjODNcdWM3NzQgXHViYjM4XHVjODFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYjBcdWJkMDlcdWM2YjBcdWI5YWNcdWM3NTggXHVjODE1XHVjNzU4XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuIFx1YzBiMFx1YmQwOVx1YzZiMFx1YjlhY1x1YjI5NCBcdWFjMTlcdWM3NDAgXHViMTkyXHVjNzc0XHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2E5XHVjNzkwIFx1ZDYzOVx1Yzc0MCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVhY2E5XHVjNzkwXHViNGU0XHVjNzU4IFx1YzlkMVx1ZDU2OVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoXHVjNWVjXHVhZTMwXHVjMTFjICZxdW90O1x1Yzc3OFx1YzgxMVx1ZDU1OFx1YjJlNCZxdW90O1x1Yzc1OCBcdWM4MTVcdWM3NThcdWIyOTQgWFx1Yzg4Y1x1ZDQ1YyBcdWNjMjhcdWM3NzRcdWM2NDAgWVx1Yzg4Y1x1ZDQ1YyBcdWNjMjhcdWM3NzQgXHViYWE4XHViNDUwIDEgXHVjNzc0XHVkNTU4XHVjNzdjIFx1YWNiZFx1YzZiMFx1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWNcdWIyZTQuKSBcdWI2MTBcdWQ1NWMgXHVjMGIwXHViZDA5XHVjNmIwXHViOWFjXHVjNjQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFjYTlcdWM3OTBcdWIyOTQgXHViYWE4XHViNDUwIFx1YzBiMFx1YmQwOVx1YzZiMFx1YjlhY1x1Yzc1OCBcdWIxOTJcdWM3NzRcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNTQ0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVhY2E5XHVjNzkwIFx1YjBiNFx1YzVkMCBcdWMwYjBcdWJkMDlcdWM2YjBcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1Y2QxZCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOKDEgJmx0OyBOICZsZTsgMTAwKSwgTSgxICZsdDsgTSAmbGU7IDcwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IE1cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHVhY2E5XHVjNzkwXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YjI5NCA1MDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBiMFx1YmQwOVx1YzZiMFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEyNDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHdWFyZGluZyB0aGUgRmFybSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIGZhcm0gaGFzIG1hbnkgaGlsbHMgdXBvbiB3aGljaCBGYXJtZXIgSm9obiB3b3VsZCBsaWtlIHRvIHBsYWNlIGd1YXJkcyB0byBlbnN1cmUgdGhlIHNhZmV0eSBvZiBoaXMgdmFsdWFibGUgbWlsay1jb3dzLjxcL3A+XHJcblxyXG48cD5IZSB3b25kZXJzIGhvdyBtYW55IGd1YXJkcyBoZSB3aWxsIG5lZWQgaWYgaGUgd2lzaGVzIHRvIHB1dCBvbmUgb24gdG9wIG9mIGVhY2ggaGlsbC4gSGUgaGFzIGEgbWFwIHN1cHBsaWVkIGFzIGEgbWF0cml4IG9mIGludGVnZXJzOyB0aGUgbWF0cml4IGhhcyBOICgxICZsdDsgTiAmbHQ7PSAxMDApIHJvd3MgYW5kIE0gKDEgJmx0OyBNICZsdDs9IDcwKSBjb2x1bW5zLiBFYWNoIG1lbWJlciBvZiB0aGUgbWF0cml4IGlzIGFuIGFsdGl0dWRlIEhfaWogKDAgJmx0Oz0gSF9paiAmbHQ7PSAxMCwwMDApLiBIZWxwIGhpbSBkZXRlcm1pbmUgdGhlIG51bWJlciBvZiBoaWxsdG9wcyBvbiB0aGUgbWFwLjxcL3A+XHJcblxyXG48cD5BIGhpbGx0b3AgaXMgb25lIG9yIG1vcmUgYWRqYWNlbnQgbWF0cml4IGVsZW1lbnRzIG9mIHRoZSBzYW1lIHZhbHVlIHN1cnJvdW5kZWQgZXhjbHVzaXZlbHkgYnkgZWl0aGVyIHRoZSBlZGdlIG9mIHRoZSBtYXAgb3IgZWxlbWVudHMgd2l0aCBhIGxvd2VyIChzbWFsbGVyKSBhbHRpdHVkZS4gVHdvIGRpZmZlcmVudCBlbGVtZW50cyBhcmUgYWRqYWNlbnQgaWYgdGhlIG1hZ25pdHVkZSBvZiBkaWZmZXJlbmNlIGluIHRoZWlyIFggY29vcmRpbmF0ZXMgaXMgbm8gZ3JlYXRlciB0aGFuIDEgYW5kIHRoZSBtYWduaXR1ZGUgb2YgZGlmZmVyZW5jZXMgaW4gdGhlaXIgWSBjb29yZGluYXRlcyBpcyBhbHNvIG5vIGdyZWF0ZXIgdGhhbiAxLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4gYW5kIE08XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5OKzE6IExpbmUgaSsxIGRlc2NyaWJlcyByb3cgaSBvZiB0aGUgbWF0cml4IHdpdGggTSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IEhfaWo8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgaW50ZWdlciB0aGF0IHNwZWNpZmllcyB0aGUgbnVtYmVyIG9mIGhpbGx0b3BzPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO November 2008 Contest > Bronze 2번

  • 문제를 번역한 사람: author6