Contain the Virus

Problem Statement

Contain the Virus Problem Description You have just been appointed Health Incharge of a district. Your first task is to contain the spread of an infection by building walls that separate infected areas from healthy ones. The district is a grid with N rows and M columns. Each cell is one area and holds 0 (a healthy area) or 1 (an infected area). A wall can be erected between any two adjacent areas, on their shared boundary. An infected region is a block of infected cells connected through the four directions East, West, North and South. The days proceed as follows: Because resources are limited, on each day you install walls around exactly one infected region, sealing it off completely. That region needs one wall for every shared boundary between one of its cells and a healthy cell. A region that has been walled in never spreads again, and its walls are never removed. The region you seal on a day is the one that threatens the most healthy areas, that is, the region adjacent to the large