Problem Statement

You have been recently appointed as the Health Incharge of a district. Your first task is to contain the spread of Covid cases in your district by building walls to separate the infected areas from the healthy areas. To keep matters simple, the district is represented in the form of a grid of size N x M . Each area in the district, represented by a cell in the grid, is assigned a value of 0 or 1 , where 0 represents a healthy area, and 1 represents an infected area. A wall can be erected between any two adjacent areas, on a shared boundary. Since you have limited resources, in one day you can install walls around only one infected region (a continuous block of infected cells connected in the four directions East, West, North and South). You always choose the region that threatens the most healthy areas - that is, the region which is adjacent to the largest number of distinct healthy cells. It is guaranteed that there is never a tie for that choice. If there is no wall around an infecte