URI Online Judge | 2687

Bacterial Domination

By Samuel Lucas Santos Gomes, IFSULDEMINAS BR Brazil

Timelimit: 1

The Federal Institute of the South of Minas (IF), Muzambinho campus opened vacancies for the new superior course: Veterinary Medicine. The coordinator of the course already anticipated some problems with the studied bacteria, once that is inevitable that a bowl of bacteria falls to the ground. It would be difficult to control them if this situation happened because, for the application of the antidote it is necessary a proportionality, in addition, it must be thrown around the bacteria, killing from the outside to inside.

Beyond to an exact amount, the antidote has to be thrown around the bacteria, so the area of the bacteria needs to be calculated to the coordinator can apply the right dose. The area of a bacterium is given in a grid(x, y) and in it, the coordinator marks the edge of the bacterium represented by 1. Through this, the area of ​the bacterium is given by (perimeter (edge ​​(1)) + content the inner side of the border or is the number of zeros surrounded by 1) divided by two, a simple average.

Because of your good reputation, she asked you to develop an application that solves this problem. Worth some extra points, develop the algorithm capable of calculating the area dominated by bacteria, which has very bizarre formats, outlined by the coordinator so that the application of the antidote has resulted.

Input

The input has Q (0 < Q <100) amounts of exposed bacteria, and then a small description of the area, composed of an integer L (0 < L <15) indicating the width and height of the grid and finally the grid LxL) with the edge drawing of the bacterium.

Output

As informed, display the dominated area with two decimal places.

Input Sample Output Sample

2
8
0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 1 1 0 0 1 0
0 0 0 1 0 0 1 0
0 0 1 1 0 0 1 0
0 0 0 1 1 1 0 0
0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0
9
1 0 0 1 0 1 0 0 1
0 1 0 1 0 1 0 1 0
0 0 1 1 1 1 1 0 0
0 1 1 0 0 0 1 1 0
0 0 1 0 0 0 1 0 0
0 1 1 0 0 0 1 1 0
0 1 0 0 0 0 0 1 0
0 1 1 1 1 1 1 1 0
1 0 0 1 0 1 0 0 1

13.00
25.00