#P4961. 小埋与扫雷

    ID: 3967 Type: RemoteJudge 1000ms 250MiB Tried: 0 Accepted: 0 Difficulty: 2 Uploaded By: Tags>模拟深度优先搜索,DFS

小埋与扫雷

题目背景

小埋总是在家中打游戏,一天,她突然想玩Windows自带的扫雷,在一旁的哥哥看见了,想起了自己小时候信息课在机房玩扫雷的日子,便兴致勃勃地开始教小埋扫雷。然而,小埋还是不明白 3bv\mathrm{3bv}(Bechtel's Board Benchmark Value,每局将所有非雷的方块点开所需最少左键点击数,参见扫雷网的教程 )怎么算,于是她找到了你。

题目描述

小埋会告诉你一盘扫雷,用一个 n×mn\times m 的矩阵表示,11 是雷 ,00 不是雷,请你告诉她这盘扫雷的 3bv\mathrm{3bv}

周围八格没有“雷”且自身不是“雷”的方格称为“空格”,周围八格有“雷”且自身不是“雷”的方格称为“数字”,由“空格”组成的八连通块称为一个“空”。3bv= \mathrm{3bv}=\ 周围八格没有“空格”的“数字”个数++“空"的个数。

如果看不懂上面的计算方式,可以看题目背景中给出的教程,或者看下面的样例解释。

注:八连通

输入格式

第一行有两个整数 nnmm,代表这盘扫雷是一个 n×mn \times m 的矩阵。

后面的 nn 行每行有 mm 个整数,表示这个矩阵,每个数字为 001111 代表是雷,00 代表不是雷。

输出格式

一个整数,代表这盘扫雷的 3bv\mathrm{3bv}

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

提示

1n, m10001\le n,\ m\le 1000

样例解释