Garden Barriers

You are given a garden represented as an M × N grid. Each cell of the grid contains either a 1 (denoting a plant) or a 0 (denoting an empty cell). The plants want to spread to adjacent cells (up, down, left, right), but we want to contain them by building barriers.

Your task is to calculate the minimum number of barriers required to enclose all the plants such that they cannot spread further. A barrier is required for each adjacent empty cell that is in contact with any plant, with the following condition:

For every plant cell, perform a search (using breadth-first search) to count all reachable adjacent empty cells. More formally, if we denote the garden grid as \(G\) with dimensions \(M \times N\), for every cell \(G_{i,j} = 1\) that has not been processed, traverse its connected component by only moving from a plant cell to an adjacent empty cell (i.e. a cell \(G_{x,y} = 0\)). Each newly reached empty cell contributes one barrier.

Note: If the garden has no plants or if all cells are plants, then no barrier is needed.

inputFormat

The first line of input contains two integers \(M\) and \(N\), representing the number of rows and columns in the garden, respectively. The next \(M\) lines each contain \(N\) space-separated integers (either 0 or 1) representing the garden grid.

Input is provided via standard input (stdin).

outputFormat

Output a single integer indicating the minimum number of barriers required. The output should be written to standard output (stdout).

3 3
0 1 0
1 0 0
0 0 1

6