Health Incharge - Flipkart Grid 8.0

Problem Preview

"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 * 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). If there is no wall around an infected area, by the next day the areas surrounding it in the four directions (East, West, North, South) also get infected. Walls once erected, cannot be removed.Your goal is to erect the walls such that as many areas as possible stay healthy and don't get infected. If there are multiple such ways to cordon off the virus, choose the one which needs the minimum number of walls. Write a program to find the minimum number of walls required to contain the virus completely, while keeping as many areas healthy as possible.Read the input from STDIN and print the output to STDOUT. Do not print arbitrary strings anywhere in the program, as these contribute to the standard output and test cases will fail. Constraints: 1 < N<= 100 1 < M <= 100 Input format: The first line contains two integers $N$ and $M$ representing rows and columns of the grid.Next $N$ lines contain $M$ space-separated integers having value 0 or 1. Output format:A single line of output contains the minimum number of walls required to contain the virus while keeping as many areas as possible un-infected."