| H - Radars |
Some radars have been installed to control the airspace of a country. Each radar covers an area of the country, and the government of the country wants to know if all the space is covered by the radars.
The airspace is divided into a square mesh of NxN zones, and each zone is labeled with an integer number. Each radar is situated in one of the zones, and the zone where a radar is situated is labeled with 0 (zero). The area of influence of each radar is determined by the values in its four neighboring zones in vertical and horizontal. If the radar is in zone (i,j), the mean of the values in zones (i-1,j), (i+1,j), (i,j-1) and (i,j+1) indicates the extent of the influence. To obtain the mean only neighbors in the NxN mesh are considered.
So, for example, in the mesh:
0
the mean is 0,
and in the mesh:
0 1
2 1
the mean corresponding to the radar is 3/2.
Positions (k,l) with Euclidean distance to (i,j) less or equal to the mean (as computed above) are in the influence area of the radar in position (i,j).
We want to count the number of zones not controlled by any radar.
The input begins with a line where the number of test cases (T) is indicated. The data for each test case appear in successive lines. For each test case, the first line contains the dimension of the airspace (N, and there are N by N zones). Next, there are N lines, each with N integers greater or equal to zero, separated by a space.
The output consists of T lines, one for each test case. For each case, the number of zones not controlled by any radar is represented.
2
4
1 2 0 0
0 1 1 0
1 1 2 0
0 1 1 1
5
1 1 0 1 1
2 1 2 0 1
2 2 1 0 0
1 2 0 1 1
1 0 2 1 1
2
7
OMP'11
Facultad
de Informatica
Universidad
de Murcia (SPAIN)