minimum cost for communication zone

Consider a rectangular state of a country. The dimension of the state is M units x N units. The state is divided in M*N cities of dimension 1 unit x 1 unit. See the example.

As shown in the above example state is 4 unit x 5 unit and there are 4*5=20 cities of 1 unit x 1 unit. Some of the cities have well-established communication and some of the cities have no communication at all. These are shown in the above figure with green and red color respectively.

Two cities X and Y (Both should be green in color) can communicate with each other if they are directly connected to each other or they are connected to cities X1 and Y1 respectively such that X1 and Y1 are connected. Two cities are said to be directly connected if they share an edge or a corner. So city at (3,1) can communicate to city at (2, 1), (1, 1), (1, 2), (2, 2) and (4, 2). These all connected parts cumulatively form a communication zone.


Cost for method 1 is 10+10+10=30 Cost for method 2 is only 2 cost of rows are separated by '#' and columns are separated by '@'

Sample TestCase 1 Input -1@10@-1#10@2@10#-1@10@-1 Output 2