시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 126 35 30 36.585%

문제

상근이는 큰 지도를 만드는 회사에서 일하고 있다. 상근이가 맡은 일은 풍경에서 산의 정상을 찾는 일이다. 정상을 찾는 일은 매우 어렵다. 다음과 같은 예제를 이용해서 입력 예제로 주어진 풍경에서 정상을 찾는 방법을 알아보자.

입력으로 주어진 예제에서 높이가 3보다 높은 곳은 없기 때문에 높이가 3인 곳은 정상이다. 높이가 3인 정상의 왼쪽에는 높이가 2인 점이 있지만, 이 곳은 정상이 아니다. 그 이유는 땅 (높이 0)으로 내려가지 않고 다시 높이가 3인 곳으로 올라갈 수 있기 때문이다. 높이 3 정상의 오른쪽에 있는 높이가 2인 곳은 정상이다. 그 이유는 높이가 3인 곳으로 올라가기 위해서 높이가 0으로 내려갔다가 다시 올라가야 하기 때문이다.

위의 에를 응용해서 상근이는 d-정상이라는 개념을 도입했다. 높이가 h인 어떤 점이 d-정상이 되려면, 그 점에서 출발해서 높이가 h-d보다 작거나 같은 곳을 방문하지 않고 더 높은 곳을 갈 수 없어야 한다.

각 점의 높이가 주어졌을 때, d-정상의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어지며, 테스트 케이스의 수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에 지도의 크기 h, w와 d가 주어진다. (1 ≤ h, w ≤ 500, 1 ≤ d ≤ 1,000,000,000) 다음 h개 줄에는 (x, y)의 높이 h가 주어진다. (0 ≤ h ≤ 1,000,000,000)

출력

각 테스트 케이스마다 d-정상의 수를 출력한다.

예제 입력 1

1
6 10 2
0 0 0 0 0 0 0 0 0 0
0 1 2 1 1 1 1 0 1 0
0 2 1 2 1 3 1 0 0 0
0 1 2 1 3 3 1 1 0 0
0 2 1 2 1 1 1 0 2 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjM2OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYzEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQwNzAgXHVjOWMwXHViM2M0XHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ2OGNcdWMwYWNcdWM1ZDBcdWMxMWMgXHVjNzdjXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjllMVx1Yzc0MCBcdWM3N2NcdWM3NDAgXHVkNDhkXHVhY2JkXHVjNWQwXHVjMTFjIFx1YzBiMFx1Yzc1OCBcdWM4MTVcdWMwYzFcdWM3NDQgXHVjYzNlXHViMjk0IFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gXHVjODE1XHVjMGMxXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWM3N2NcdWM3NDAgXHViOWU0XHVjNmIwIFx1YzViNFx1YjgzNVx1YjJlNC4gXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM2MDhcdWM4MWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1Yzc4NVx1YjgyNSBcdWM2MDhcdWM4MWNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDQ4ZFx1YWNiZFx1YzVkMFx1YzExYyBcdWM4MTVcdWMwYzFcdWM3NDQgXHVjYzNlXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM1NGNcdWM1NDRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YjE5Mlx1Yzc3NFx1YWMwMCAzXHViY2Y0XHViMmU0IFx1YjE5Mlx1Yzc0MCBcdWFjZjNcdWM3NDAgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIxOTJcdWM3NzRcdWFjMDAgM1x1Yzc3OCBcdWFjZjNcdWM3NDAgXHVjODE1XHVjMGMxXHVjNzc0XHViMmU0LiBcdWIxOTJcdWM3NzRcdWFjMDAgM1x1Yzc3OCBcdWM4MTVcdWMwYzFcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1YWMwMCAyXHVjNzc4IFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1Yzc3NCBcdWFjZjNcdWM3NDAgXHVjODE1XHVjMGMxXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWI1NDUgKFx1YjE5Mlx1Yzc3NCAwKVx1YzczY1x1Yjg1YyBcdWIwYjRcdWI4MjRcdWFjMDBcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YjJlNFx1YzJkYyBcdWIxOTJcdWM3NzRcdWFjMDAgM1x1Yzc3OCBcdWFjZjNcdWM3M2NcdWI4NWMgXHVjNjJjXHViNzdjXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWIxOTJcdWM3NzQgMyBcdWM4MTVcdWMwYzFcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWFjMDAgMlx1Yzc3OCBcdWFjZjNcdWM3NDAgXHVjODE1XHVjMGMxXHVjNzc0XHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1YWMwMCAzXHVjNzc4IFx1YWNmM1x1YzczY1x1Yjg1YyBcdWM2MmNcdWI3N2NcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjE5Mlx1Yzc3NFx1YWMwMCAwXHVjNzNjXHViODVjIFx1YjBiNFx1YjgyNFx1YWMxNFx1YjJlNFx1YWMwMCBcdWIyZTRcdWMyZGMgXHVjNjJjXHViNzdjXHVhYzAwXHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM1ZDBcdWI5N2MgXHVjNzUxXHVjNmE5XHVkNTc0XHVjMTFjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBkLVx1YzgxNVx1YzBjMVx1Yzc3NFx1Yjc3Y1x1YjI5NCBcdWFjMWNcdWIxNTBcdWM3NDQgXHViM2M0XHVjNzg1XHVkNTg4XHViMmU0LiBcdWIxOTJcdWM3NzRcdWFjMDAgaFx1Yzc3OCBcdWM1YjRcdWI1YTQgXHVjODEwXHVjNzc0IGQtXHVjODE1XHVjMGMxXHVjNzc0IFx1YjQxOFx1YjgyNFx1YmE3NCwgXHVhZGY4IFx1YzgxMFx1YzVkMFx1YzExYyBcdWNkOWNcdWJjMWNcdWQ1NzRcdWMxMWMgXHViMTkyXHVjNzc0XHVhYzAwIGgtZFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YWNmM1x1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YjM1NCBcdWIxOTJcdWM3NDAgXHVhY2YzXHVjNzQ0IFx1YWMwOCBcdWMyMTggXHVjNWM2XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzgxMFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgZC1cdWM4MTVcdWMwYzFcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHViMjk0IDEwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWQwNmNcdWFlMzAgaCwgd1x1YzY0MCBkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBoLCB3ICZsZTsgNTAwLCAxICZsZTsgZCAmbGU7IDEsMDAwLDAwMCwwMDApIFx1YjJlNFx1Yzc0YyBoXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCAoeCwgeSlcdWM3NTggXHViMTkyXHVjNzc0IGhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IGggJmxlOyAxLDAwMCwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IGQtXHVjODE1XHVjMGMxXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY5NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN1bW1pdHMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSByZWNlbnRseSBzdGFydGVkIHdvcmtpbmcgZm9yIHRoZSBsYXJnZXN0IG1hcCBkcmF3aW5nIGNvbXBhbnkgaW4gdGhlIE5ldGhlcmxhbmRzLiBQYXJ0IG9mIHlvdXIgam9iIGlzIHRvIGRldGVybWluZSB3aGF0IHRoZSBzdW1taXRzIGluIGEgcGFydGljdWxhciBsYW5kc2NhcGUgYXJlLiBVbmZvcnR1bmF0ZWx5LCBpdCBpcyBub3Qgc28gZWFzeSB0byBkZXRlcm1pbmUgd2hpY2ggcG9pbnRzIGFyZSBzdW1taXRzIGFuZCB3aGljaCBhcmUgbm90LCBiZWNhdXNlIHdlIGRvIG5vdCB3YW50IHRvIGNhbGwgYSBzbWFsbCBodW1wIGEgc3VtbWl0LiBGb3IgZXhhbXBsZSBsb29rIGF0IHRoZSBsYW5kc2NhcGUgZ2l2ZW4gYnkgdGhlIHNhbXBsZSBpbnB1dC48XC9wPlxyXG5cclxuPHA+V2UgY2FsbCB0aGUgcG9pbnRzIG9mIGhlaWdodCAzIHN1bW1pdHMsIHNpbmNlIHRoZXJlIGFyZSBubyBoaWdoZXIgcG9pbnRzLiBCdXQgYWx0aG91Z2ggdGhlIHBvaW50cyBvZiBoZWlnaHQgMiwgd2hpY2ggYXJlIHRvIHRoZSBsZWZ0IG9mIHRoZSBzdW1taXQgb2YgaGVpZ2h0IDMsIGFyZSBhbGwgaGlnaGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlaXIgaW1tZWRpYXRlIG5laWdoYm91cnMsIHdlIGRvIG5vdCB3YW50IHRvIGNhbGwgdGhlbSBzdW1taXRzLCBiZWNhdXNlIHdlIGNhbiByZWFjaCBhIGhpZ2hlciBwb2ludCBmcm9tIHRoZW0gd2l0aG91dCBnb2luZyB0byBsb3cgKHRoZSBzdW1taXRzIG9mIGhlaWdodCAzKS4gSW4gY29udHJhc3QsIHdlIGRvIHdhbnQgdG8gY2FsbCB0aGUgYXJlYSBvZiBoZWlnaHQgMiBvbiB0aGUgcmlnaHQgYSBzdW1taXQsIHNpbmNlIGlmIHdlIHdvdWxkIHdhbnQgdG8gd2FsayB0byB0aGUgc3VtbWl0IG9mIGhlaWdodCAzLCB3ZSBcdWZiMDFyc3QgaGF2ZSB0byBkZXNjZW5kIHRvIGEgcG9pbnQgd2l0aCBoZWlnaHQgMC48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgdGhlIGFib3ZlIGV4YW1wbGUsIHdlIGludHJvZHVjZSB0aGUgY29uY2VwdCBvZiBhIGQtc3VtbWl0LiBBIHBvaW50LCB3aXRoIGhlaWdodCBoLCBpcyBhIGQtc3VtbWl0IGlmIGFuZCBvbmx5IGlmIGl0IGlzIGltcG9zc2libGUgdG8gcmVhY2ggYSBoaWdoZXIgcG9pbnQgd2l0aG91dCBnb2luZyB0aHJvdWdoIGFuIGFyZWEgd2l0aCBoZWlnaHQgc21hbGxlciB0aGFuIG9yIGVxdWFsIHRvIGggJm1pbnVzOyBkLjxcL3A+XHJcblxyXG48cD5UaGUgcHJvYmxlbSBpcywgZ2l2ZW4gYSByZWN0YW5ndWxhciBncmlkIG9mIGludGVnZXIgaGVpZ2h0cyBhbmQgYW4gaW50ZWdlciBkLCB0byBcdWZiMDFuZCB0aGUgbnVtYmVyIG9mIGQtc3VtbWl0cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdGhyZWUgaW50ZWdlcnMgMSAmbGU7IGggJmxlOyA1MDAsIDEgJmxlOyB3ICZsZTsgNTAwIGFuZCAxICZsZTsgZCAmbGU7IDEgMDAwIDAwMCAwMDAuIGggYW5kIHcgYXJlIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBtYXAuIGQgaXMgYXMgZGVcdWZiMDFuZWQgaW4gdGhlIHRleHQuPFwvbGk+XHJcblx0PGxpPmggbGluZXMgd2l0aCB3IGludGVnZXJzLCB3aGVyZSB0aGUgeHRoIGludGVnZXIgb24gdGhlIHl0aCBsaW5lIGRlbm90ZXMgdGhlIGhlaWdodCAwICZsZTsgaCAmbGU7IDEgMDAwIDAwMCAwMDAgb2YgdGhlIHBvaW50ICh4LCB5KS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHRoZSBudW1iZXIgb2Ygc3VtbWl0cy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2007 G번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: qwerty08