시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 166 50 36 37.500%

문제

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수가 주어지며, 테스트 케이스의 수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에 지도의 크기 n, m와 d가 주어진다. (1 ≤ n, m ≤ 500, 1 ≤ d ≤ 1,000,000,000) 다음 n개 줄에는 (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
W3sicHJvYmxlbV9pZCI6IjM2OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYzEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQwNzAgXHVjOWMwXHViM2M0XHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ2OGNcdWMwYWNcdWM1ZDBcdWMxMWMgXHVjNzdjXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjllMVx1Yzc0MCBcdWM3N2NcdWM3NDAgXHVkNDhkXHVhY2JkXHVjNWQwXHVjMTFjIFx1YzBiMFx1Yzc1OCBcdWM4MTVcdWMwYzFcdWM3NDQgXHVjYzNlXHViMjk0IFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gXHVjODE1XHVjMGMxXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWM3N2NcdWM3NDAgXHViOWU0XHVjNmIwIFx1YzViNFx1YjgzNVx1YjJlNC4gXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM2MDhcdWM4MWNcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1Yzc4NVx1YjgyNSBcdWM2MDhcdWM4MWNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1ZDQ4ZFx1YWNiZFx1YzVkMFx1YzExYyBcdWM4MTVcdWMwYzFcdWM3NDQgXHVjYzNlXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM1NGNcdWM1NDRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YjE5Mlx1Yzc3NFx1YWMwMCAzXHViY2Y0XHViMmU0IFx1YjE5Mlx1Yzc0MCBcdWFjZjNcdWM3NDAgXHVjNWM2XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIxOTJcdWM3NzRcdWFjMDAgM1x1Yzc3OCBcdWFjZjNcdWM3NDAgXHVjODE1XHVjMGMxXHVjNzc0XHViMmU0LiBcdWIxOTJcdWM3NzRcdWFjMDAgM1x1Yzc3OCBcdWM4MTVcdWMwYzFcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1YWMwMCAyXHVjNzc4IFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWM5YzBcdWI5Y2MsIFx1Yzc3NCBcdWFjZjNcdWM3NDAgXHVjODE1XHVjMGMxXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVhZGY4IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWI1NDUgKFx1YjE5Mlx1Yzc3NCAwKVx1YzczY1x1Yjg1YyBcdWIwYjRcdWI4MjRcdWFjMDBcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YjJlNFx1YzJkYyBcdWIxOTJcdWM3NzRcdWFjMDAgM1x1Yzc3OCBcdWFjZjNcdWM3M2NcdWI4NWMgXHVjNjJjXHViNzdjXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LiBcdWIxOTJcdWM3NzQgMyBcdWM4MTVcdWMwYzFcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIxOTJcdWM3NzRcdWFjMDAgMlx1Yzc3OCBcdWFjZjNcdWM3NDAgXHVjODE1XHVjMGMxXHVjNzc0XHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IFx1YjE5Mlx1Yzc3NFx1YWMwMCAzXHVjNzc4IFx1YWNmM1x1YzczY1x1Yjg1YyBcdWM2MmNcdWI3N2NcdWFjMDBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjE5Mlx1Yzc3NFx1YWMwMCAwXHVjNzNjXHViODVjIFx1YjBiNFx1YjgyNFx1YWMxNFx1YjJlNFx1YWMwMCBcdWIyZTRcdWMyZGMgXHVjNjJjXHViNzdjXHVhYzAwXHVjNTdjIFx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM2MDhcdWI5N2MgXHVjNzUxXHVjNmE5XHVkNTc0XHVjMTFjJm5ic3A7XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IGQtXHVjODE1XHVjMGMxXHVjNzc0XHViNzdjXHViMjk0IFx1YWMxY1x1YjE1MFx1Yzc0NCBcdWIzYzRcdWM3ODVcdWQ1ODhcdWIyZTQuIFx1YjE5Mlx1Yzc3NFx1YWMwMCBoXHVjNzc4IFx1YzViNFx1YjVhNCBcdWM4MTBcdWM3NzQgZC1cdWM4MTVcdWMwYzFcdWM3NzQgXHViNDE4XHViODI0XHViYTc0LCBcdWFkZjggXHVjODEwXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU3NFx1YzExYyBcdWIxOTJcdWM3NzRcdWFjMDAgaC1kXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVhY2YzXHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHViMzU0IFx1YjE5Mlx1Yzc0MCBcdWFjZjNcdWM3NDQgXHVhYzA4IFx1YzIxOCBcdWM1YzZcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjODEwXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBkLVx1YzgxNVx1YzBjMVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWIyOTQgMTAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMwXHViM2M0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBuLCBtXHVjNjQwIGRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IG4sIG0gJmxlOyA1MDAsIDEgJmxlOyBkICZsZTsgMSwwMDAsMDAwLDAwMCkgXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0ICh4LCB5KVx1Yzc1OCBcdWIxOTJcdWM3NzQgaFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgaCAmbGU7IDEsMDAwLDAwMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgZC1cdWM4MTVcdWMwYzFcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3VtbWl0cyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IHJlY2VudGx5IHN0YXJ0ZWQgd29ya2luZyBmb3IgdGhlIGxhcmdlc3QgbWFwIGRyYXdpbmcgY29tcGFueSBpbiB0aGUgTmV0aGVybGFuZHMuIFBhcnQgb2YgeW91ciBqb2IgaXMgdG8gZGV0ZXJtaW5lIHdoYXQgdGhlIHN1bW1pdHMgaW4gYSBwYXJ0aWN1bGFyIGxhbmRzY2FwZSBhcmUuIFVuZm9ydHVuYXRlbHksIGl0IGlzIG5vdCBzbyBlYXN5IHRvIGRldGVybWluZSB3aGljaCBwb2ludHMgYXJlIHN1bW1pdHMgYW5kIHdoaWNoIGFyZSBub3QsIGJlY2F1c2Ugd2UgZG8gbm90IHdhbnQgdG8gY2FsbCBhIHNtYWxsIGh1bXAgYSBzdW1taXQuIEZvciBleGFtcGxlIGxvb2sgYXQgdGhlIGxhbmRzY2FwZSBnaXZlbiBieSB0aGUgc2FtcGxlIGlucHV0LjxcL3A+XHJcblxyXG48cD5XZSBjYWxsIHRoZSBwb2ludHMgb2YgaGVpZ2h0IDMgc3VtbWl0cywgc2luY2UgdGhlcmUgYXJlIG5vIGhpZ2hlciBwb2ludHMuIEJ1dCBhbHRob3VnaCB0aGUgcG9pbnRzIG9mIGhlaWdodCAyLCB3aGljaCBhcmUgdG8gdGhlIGxlZnQgb2YgdGhlIHN1bW1pdCBvZiBoZWlnaHQgMywgYXJlIGFsbCBoaWdoZXIgdGhhbiBvciBlcXVhbCB0byB0aGVpciBpbW1lZGlhdGUgbmVpZ2hib3Vycywgd2UgZG8gbm90IHdhbnQgdG8gY2FsbCB0aGVtIHN1bW1pdHMsIGJlY2F1c2Ugd2UgY2FuIHJlYWNoIGEgaGlnaGVyIHBvaW50IGZyb20gdGhlbSB3aXRob3V0IGdvaW5nIHRvIGxvdyAodGhlIHN1bW1pdHMgb2YgaGVpZ2h0IDMpLiBJbiBjb250cmFzdCwgd2UgZG8gd2FudCB0byBjYWxsIHRoZSBhcmVhIG9mIGhlaWdodCAyIG9uIHRoZSByaWdodCBhIHN1bW1pdCwgc2luY2UgaWYgd2Ugd291bGQgd2FudCB0byB3YWxrIHRvIHRoZSBzdW1taXQgb2YgaGVpZ2h0IDMsIHdlIFx1ZmIwMXJzdCBoYXZlIHRvIGRlc2NlbmQgdG8gYSBwb2ludCB3aXRoIGhlaWdodCAwLjxcL3A+XHJcblxyXG48cD5BZnRlciB0aGUgYWJvdmUgZXhhbXBsZSwgd2UgaW50cm9kdWNlIHRoZSBjb25jZXB0IG9mIGEgZC1zdW1taXQuIEEgcG9pbnQsIHdpdGggaGVpZ2h0IGgsIGlzIGEgZC1zdW1taXQgaWYgYW5kIG9ubHkgaWYgaXQgaXMgaW1wb3NzaWJsZSB0byByZWFjaCBhIGhpZ2hlciBwb2ludCB3aXRob3V0IGdvaW5nIHRocm91Z2ggYW4gYXJlYSB3aXRoIGhlaWdodCBzbWFsbGVyIHRoYW4gb3IgZXF1YWwgdG8gaCAmbWludXM7IGQuPFwvcD5cclxuXHJcbjxwPlRoZSBwcm9ibGVtIGlzLCBnaXZlbiBhIHJlY3Rhbmd1bGFyIGdyaWQgb2YgaW50ZWdlciBoZWlnaHRzIGFuZCBhbiBpbnRlZ2VyIGQsIHRvIFx1ZmIwMW5kIHRoZSBudW1iZXIgb2YgZC1zdW1taXRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aHJlZSBpbnRlZ2VycyAxICZsZTsgaCAmbGU7IDUwMCwgMSAmbGU7IHcgJmxlOyA1MDAgYW5kIDEgJmxlOyBkICZsZTsgMSAwMDAgMDAwIDAwMC4gaCBhbmQgdyBhcmUgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIG1hcC4gZCBpcyBhcyBkZVx1ZmIwMW5lZCBpbiB0aGUgdGV4dC48XC9saT5cclxuXHQ8bGk+aCBsaW5lcyB3aXRoIHcgaW50ZWdlcnMsIHdoZXJlIHRoZSB4dGggaW50ZWdlciBvbiB0aGUgeXRoIGxpbmUgZGVub3RlcyB0aGUgaGVpZ2h0IDAgJmxlOyBoICZsZTsgMSAwMDAgMDAwIDAwMCBvZiB0aGUgcG9pbnQgKHgsIHkpLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdGhlIG51bWJlciBvZiBzdW1taXRzLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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