Coding round questions asked by various companies recently that I am not able to solve

Правка en1, от ardh1999, 2020-10-19 11:11:37

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)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ardh1999 2020-10-19 11:11:37 1055 I want good approaches (published)