← 返回 nvidia 的题目列表Tree Planting on a Grid (no adjacent trees)
类型：online_judge
Given an m x n grid grid representing land:
1 means an existing tree
0 means empty
You may plant new trees on empty cells, subject to:
No two trees (existing or newly planted) may be adjacent in the 4-neighborhood (up/down/left/right).
Compute the maximum number of additional trees you can plant.
Input (stdin):
First line: m n
Next m lines: n integers (0/1)
Output (stdout):
One line: maximum additional trees
Constraints: 1 <= m, n <= 200.
Example
Input
2 3
0 0 0
0 0 0
Output
3