1.company name- compass

Q1) Mobile Tower Coverage Given an area represented as an 2-d square matrix with '1' representing a plot with building and '0' representing a vacant plot. Identify the minimum number of mobile towers required to cover all of the occupied plots.

When a mobile tower is placed in a plot, the tower covers the area of the plot it is placed on along with the adjacent plots on left, right, top and bottom. For example when a mobile tower is placed on plot (1,1) in a 3*3 matrix, then the mobile tower covers the plots (1,1) ,(1,0),(0,1),(1,2),(2,1).

First line of input representing the size of the square matrix (3 < N < 100).subsequent lines represent the matrix rows in a space separated manner.

sample input 1: 4 0 0 0 0 0 1 1 0 0 1 1 1 0 1 0 0 sample output 1: 2

Explanation :

In the sample some of the possible placements that results in coverage with minimal count is- (2,1) and (2,2) or (2,1) and (1,3)