Minimum Operations to Clear Field

Problem Statement: Given a two-dimensional grid that represents a field, each cell in the grid is marked with either a stone (represented by 1) or empty (represented by 0). In one operation, you can remove all stones within any chosen rectangular subregion of the grid. Your task is to determine the minimum number of operations required to clear all the stones from the field.

Note: Two stones are considered connected if they are adjacent horizontally or vertically. Essentially, each operation can clear a connected component of stones. Mathematically, if you have several connected groups, the minimum number of operations equals the number of these groups. In other words, if we denote the number of connected components by \(k\), then the answer is \(k\).

Input/Output Methods: The input will be provided from standard input (stdin), and your output should be printed to standard output (stdout).

inputFormat

The input consists of multiple datasets. For each dataset, the first line contains two integers R and C, where R is the number of rows and C is the number of columns of the grid. Following this, there are R lines each containing C integers (either 0 or 1) separated by spaces. Datasets continue until a line with "0 0" is encountered, which signals the end of input.

outputFormat

For each dataset, output a single integer on a new line, representing the minimum number of operations required to clear all stones from the grid.## sample

2 3
1 0 1
0 1 0
3 3
1 1 1
1 1 1
1 1 1
0 0

3
1