시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 88 41 31 48.438%

문제

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

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

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

입력

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

출력

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

예제 입력 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

힌트

W3sicHJvYmxlbV9pZCI6IjEyNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxOGRcdWM3YTUgXHVhZDAwXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHViYmZjXHVjMmRkXHVjNzc0XHVhYzAwIFx1YWQwMFx1YjlhY1x1ZDU1OFx1YjI5NCBcdWIxOGRcdWM3YTVcdWM3NDAgTipNIFx1YWNhOVx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJiZmNcdWMyZGRcdWM3NzRcdWIyOTQgXHViMThkXHVjN2E1XHVjNzQ0IFx1YWQwMFx1YjlhY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjMGIwXHViZDA5XHVjNmIwXHViOWFjXHViOWM4XHViMmU0IGd1YXJkXHViOTdjIFx1YmMzMFx1Y2U1OFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWM3MDRcdWQ1NzQgXHViMThkXHVjN2E1XHVjNWQwIFx1YzBiMFx1YmQwOVx1YzZiMFx1YjlhY1x1YWMwMCBcdWNkMWQgXHViYTg3IFx1YWMxYyBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVjMTM4XHViMjk0IFx1YWM4M1x1Yzc3NCBcdWJiMzhcdWM4MWNcdWIyZTQuPFwvcD5cclxuPHA+XHVjMGIwXHViZDA5XHVjNmIwXHViOWFjXHVjNzU4IFx1YzgxNVx1Yzc1OFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiBcdWMwYjBcdWJkMDlcdWM2YjBcdWI5YWNcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YjE5Mlx1Yzc3NFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YWNhOVx1Yzc5MCBcdWQ2MzlcdWM3NDAgXHVjNzc4XHVjODExXHVkNTVjIFx1YWNhOVx1Yzc5MFx1YjRlNFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKFx1YzVlY1x1YWUzMFx1YzExYyAmcXVvdDtcdWM3NzhcdWM4MTFcdWQ1NThcdWIyZTQmcXVvdDtcdWM3NTggXHVjODE1XHVjNzU4XHViMjk0IFhcdWM4OGNcdWQ0NWMgXHVjYzI4XHVjNzc0XHVjNjQwIFlcdWM4OGNcdWQ0NWMgXHVjYzI4XHVjNzc0IFx1YmFhOFx1YjQ1MCAxIFx1Yzc3NFx1ZDU1OFx1Yzc3YyBcdWFjYmRcdWM2YjBcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LikgXHViNjEwXHVkNTVjIFx1YzBiMFx1YmQwOVx1YzZiMFx1YjlhY1x1YzY0MCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVhY2E5XHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWMwYjBcdWJkMDlcdWM2YjBcdWI5YWNcdWM3NTggXHViMTkyXHVjNzc0XHViY2Y0XHViMmU0IFx1Yzc5MVx1YzU0NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgXHVhY2E5XHVjNzkwIFx1YjBiNFx1YzVkMCBcdWMwYjBcdWJkMDlcdWM2YjBcdWI5YWNcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1Y2QxZCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IE4oMSZsdDtOJmxlOzEwMCksIE0oMSZsdDtNJmxlOzcwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IFx1YWNhOVx1Yzc5MFx1YjRlNFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IE1cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGIwXHViZDA5XHVjNmIwXHViOWFjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMjQ1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3VhcmRpbmcgdGhlIEZhcm0iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBmYXJtIGhhcyBtYW55IGhpbGxzIHVwb24gd2hpY2ggRmFybWVyIEpvaG4gd291bGQgbGlrZSB0byBwbGFjZSBndWFyZHMgdG8gZW5zdXJlIHRoZSBzYWZldHkgb2YgaGlzIHZhbHVhYmxlIG1pbGstY293cy48XC9wPlxyXG5cclxuPHA+SGUgd29uZGVycyBob3cgbWFueSBndWFyZHMgaGUgd2lsbCBuZWVkIGlmIGhlIHdpc2hlcyB0byBwdXQgb25lIG9uIHRvcCBvZiBlYWNoIGhpbGwuIEhlIGhhcyBhIG1hcCBzdXBwbGllZCBhcyBhIG1hdHJpeCBvZiBpbnRlZ2VyczsgdGhlIG1hdHJpeCBoYXMgTiAoMSAmbHQ7IE4gJmx0Oz0gMTAwKSByb3dzIGFuZCBNICgxICZsdDsgTSAmbHQ7PSA3MCkgY29sdW1ucy4gRWFjaCBtZW1iZXIgb2YgdGhlIG1hdHJpeCBpcyBhbiBhbHRpdHVkZSBIX2lqICgwICZsdDs9IEhfaWogJmx0Oz0gMTAsMDAwKS4gSGVscCBoaW0gZGV0ZXJtaW5lIHRoZSBudW1iZXIgb2YgaGlsbHRvcHMgb24gdGhlIG1hcC48XC9wPlxyXG5cclxuPHA+QSBoaWxsdG9wIGlzIG9uZSBvciBtb3JlIGFkamFjZW50IG1hdHJpeCBlbGVtZW50cyBvZiB0aGUgc2FtZSB2YWx1ZSBzdXJyb3VuZGVkIGV4Y2x1c2l2ZWx5IGJ5IGVpdGhlciB0aGUgZWRnZSBvZiB0aGUgbWFwIG9yIGVsZW1lbnRzIHdpdGggYSBsb3dlciAoc21hbGxlcikgYWx0aXR1ZGUuIFR3byBkaWZmZXJlbnQgZWxlbWVudHMgYXJlIGFkamFjZW50IGlmIHRoZSBtYWduaXR1ZGUgb2YgZGlmZmVyZW5jZSBpbiB0aGVpciBYIGNvb3JkaW5hdGVzIGlzIG5vIGdyZWF0ZXIgdGhhbiAxIGFuZCB0aGUgbWFnbml0dWRlIG9mIGRpZmZlcmVuY2VzIGluIHRoZWlyIFkgY29vcmRpbmF0ZXMgaXMgYWxzbyBubyBncmVhdGVyIHRoYW4gMS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBNPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTisxOiBMaW5lIGkrMSBkZXNjcmliZXMgcm93IGkgb2YgdGhlIG1hdHJpeCB3aXRoIE0gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBIX2lqPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCBzcGVjaWZpZXMgdGhlIG51bWJlciBvZiBoaWxsdG9wczxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=