Problem Statement

You have been appointed Health Incharge of a district and must contain the spread of an infection by building walls that separate infected areas from healthy ones. The district is a grid of size N × M . Each cell holds 0 (a healthy area) or 1 (an infected area). A wall can be erected between any two adjacent areas, on their shared boundary. With limited resources, in one day you can install walls around only one infected region — one 4-directionally connected block of infected cells — sealing it off completely. Any infected region that is not sealed spreads: by the next day every healthy area orthogonally adjacent (East, West, North, South) to it also becomes infected. Walls, once erected, cannot be removed, and a fully walled region can never spread again. Your goal is to erect walls so that as many areas as possible stay healthy . If several strategies keep the same number of areas healthy, choose the one that needs the minimum number of walls . Write a program that