#B4263. Maximizing Cultivable Land
Maximizing Cultivable Land
Maximizing Cultivable Land
You are given a grid representing a piece of land with n rows and m columns. Each cell is either free from debris or contains debris. A cell that is free (without debris) can be cultivated if and only if all of its existing four directionally adjacent neighbors (up, down, left, right) are also free from debris.
You are allowed to remove debris from at most one cell (i.e. convert a debris cell into a free cell). Determine the maximum number of cells that can be cultivated under the optimal debris removal (or no removal) strategy.
Note: For cells on the border, only the neighbors that exist within the grid are considered.
Input Format: The grid is provided in the following format. See the input description below for details.
inputFormat
The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of rows and columns of the grid.
Each of the next n lines contains m space-separated integers. Each integer is either 0 or 1, where 0 indicates that there is no debris (i.e. the cell is initially free) and 1 indicates that the cell contains debris.
outputFormat
Output a single integer which is the maximum number of cultivable cells after removing debris from at most one cell.
sample
3 3
0 1 0
1 0 1
0 1 0
1