+1

# communication zone problem

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 1unit. 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.hence, the whole state is divided in various communication zones due to presence of nocommunication cities in state. like in above example, we have two communication zones one inleft and one in right.state government can stabilize communication in red regions but it would cause some cost andevery red region may have a different cost. in fact, there is no use of stabilizing communicationin red cities because these are very less populated area. government concern is to connect thevarious communication zones. this is possible if some of the red cities are converted into green.

10/10/2018 9:52:50 AM

+11

Is there a question hidden in there somewhere? ðŸ˜‚

+6

+6

+5