cho.shTime limit
2s
Memory limit
128 MB
You are given an N×N Minesweeper board. Some cells contain mines. Every opened non-mine cell shows how many mines are in the 8 neighboring cells around it.
In this problem, every border cell of the board is already open, and every non-border cell is still closed. Closed cells are written as #. Consider the following board.
| 1 | 1 | 1 | 0 | 0 |
| 2 | # | # | # | 1 |
| 3 | # | # | # | 1 |
| 2 | # | # | # | 1 |
| 1 | 2 | 2 | 1 | 0 |
For this board, at most 6 closed cells can contain mines. One possible placement is shown below.
| 1 | 1 | 1 | 0 | 0 |
| 2 | * | 1 | ||
| 3 | * | * | * | 1 |
| 2 | * | * | 1 | |
| 1 | 2 | 2 | 1 | 0 |
Given the board, find the maximum number of closed cells that can contain mines.
The first line contains an integer N (1 ≤ N ≤ 100).
Each of the next N lines contains a string of length N describing the board. Border cells are digits, and every closed non-border cell is written as #.
Print the maximum number of closed cells that can contain mines.