P4961 Umaru and Minesweeper

Umaru is always playing games at home. One day, she suddenly wanted to play the Minesweeper that comes with Windows. Her older brother saw this and remembered the days when he played Minesweeper in the computer lab during IT class when he was young, so he happily started teaching Umaru how to play. However, Umaru still did not understand how to compute $\mathrm{3bv}$ (Bechtel's Board Benchmark Value, the minimum number of left clicks needed to open all non-mine cells in one game; see the [tutorial on saolei.net](http://saolei.net/BBS/Title.asp?Id=227)), so she came to you. 

Umaru will tell you a Minesweeper board, represented by an $n\times m$ matrix, where $1$ means a mine and $0$ means not a mine. Please tell her the $\mathrm{3bv}$ of this board. A cell that is not a mine and has no mines in the eight surrounding cells is called an "empty cell". A cell that is not a mine and has at least one mine in the eight surrounding cells is called a "number cell". An 8-connected component consisting of "empty cells" is called an "empty area". $\mathrm{3bv}=$ (the number of "number cells" that have no "empty cells" in their eight surrounding cells) $+$ (the number of "empty areas"). If you cannot understand the computation above, you can read the tutorial given in the Background, or see the sample explanation below. Note: [8-connectivity](https://baike.baidu.com/item/%E5%85%AB%E8%BF%9E%E9%80%9A)

The first line contains two integers $n$ and $m$, meaning the Minesweeper board is an $n \times m$ matrix. The next $n$ lines each contain $m$ integers, describing the matrix. Each number is either $0$ or $1$. $1$ means the cell is a mine, and $0$ means it is not a mine.

Output one integer, representing the $\mathrm{3bv}$ of this Minesweeper board.

$1\le n,\ m\le 1000$ Translated by ChatGPT 5