Description

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

Input Format

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 Format

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

8 8
0 0 0 1 1 0 0 0 
1 0 0 1 0 0 0 1 
1 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 

13

Hint

$1\le n,\ m\le 1000$

Translated by ChatGPT 5