Time Limit: 2s Memory Limit: 256MB

题目描述

神豪 lglg 决定寻找一块风水宝地修建他的海景房。
现在它得到了一份尺寸为 \(n*m\) 的地图,地图上的每一格由一个数字描述(数字 0 表示海或湖),表示该地的海拔。
一个位置能看到海,当且仅当从这个位置往上下左右的任意一个方向看,能够看到海(注意:海拔高度一样仍然视为可以挡住视野)。
现在 lglg 想知道有多少个位置可以修建海景房(从修房的位置能看得见海)。

例:

0 0 0 0 0 0 0
0 5 8 9 0 5 0
0 7 7 7 0 0 0
0 5 8 9 0 0 0
0 0 0 0 0 0 0

在这个地图描述的区域,有两个岛,除了左边那个岛中心的“7”以外,别的位置都能看到海,因此答案为 9。

注意 :地图保证最边缘的一圈是海,与海连通的海拔为 0 的方块也是海,不与海连通的海拔为 0 的方块是湖,只看得见湖却看不见海的位置并不是一个合法的修建海景房的位置。
比如:

0 0 0 0 0
0 1 2 3 0
0 1 0 3 0
0 1 4 3 0
0 0 0 0 0

最中心的海拔为 0 的点仅仅是湖,并不是海。

保证地图面积大于 1000000 的数据不超过 5 组,其他的都是地图面积小于 10000 的数据。

输入格式

第一行是一个正整数 \(T\;(1<=T<=100)\)
对于每一组数据:
第一行是两个数 \(n,m(2 <= n, m <= 2000)\),表示地图的尺寸
接下来 \(n\)行,每行 \(m\) 个数,每个数为 0 到 1000000000 之间的整数,描述地图信息。

输出格式

对于每组测试用例,输出一行,表示可以修海景房(看得见海)的位置个数。

样例输入

2
5 7
0 0 0 0 0 0 0
0 5 8 9 0 5 0
0 7 7 7 0 0 0
0 5 8 9 0 0 0
0 0 0 0 0 0 0
5 5
0 0 0 0 0
0 1 2 3 0
0 1 0 3 0
0 1 4 3 0
0 0 0 0 0

样例输出

9
8