山高人为峰

Time Limit: 3000 MS

Memory Limit: 65535 KB

Description

给一个h*w的地图,每个位置上(x,y)(1<=x<=h,1<=y<=w)有个一数值h,代表该点(山峰)的海拔。现有一个登山爱好者,想从该地图h*w个位置上选个登山起点(sx,sy),沿上下左右四个方向走,以达到更高的山峰为成功目标。
但该登山爱好者有个嗜好,从来不走海拔小于或等于sh-d的点。其中sh为登山起点的海拔,d为他的嗜好度。
 请问在h*w的地图上有多少个点可以作为该登山爱好者的登山起点,在满足他的嗜好情况下,可以达到更高的山峰(想对于登山起点)。

Input

第一行为一个正整数t(t<=25),代表测试组数。每一组测试数据:
一行有三个整数1 ≤ h ≤ 500, 1 ≤ w ≤ 500 and 1 ≤ d ≤ 1 000 000 000. 其中h 和w 分别为地图的高和宽. d为该登山者的嗜好度。
接下来有h行w列个整数,第x行的第y个整数,代表该点的海拔(0 ≤ h ≤
 1 000 000 000)

Output

对于每一组测试数据:
输出一个整数n,以换行结尾(代表在h*w的地图上有n个点可以作为该登山爱好者的登山起点,以达到更高的山峰)

Sample Input

3
2 2 1
0 1
2 0
2 2 2
0 1
2 0
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

Sample Output

2
3
56

Hint

None

Source

张俊杰

提交代码