近期发现部分用户尝试利用判题系统的评测信息进行作弊,严重破坏了公平竞争的环境。为维护良好的交流与学习氛围,已对判题机进行了优化,当程序遇到测试点不通过时会立即返回而不评测更多测试点;并且延长提交间隔为60秒。作弊行为不仅违背了学习的初衷,还侵害了其他用户的公平权益,希望所有用户能够遵守规范,专注算法与思维能力的提升。对于恶意多次尝试的用户,我们将保留进一步处置的权利。 —— Administrator

100721 - 荧光棒

有一个由row × col块边长为1的瓷砖贴起来的墙面,大部分瓷砖都脱落了,仅存一块相连(特指左右或上下四向,对角线不算相连)且无空洞的部分,神牛弟弟要用长度1的荧光棒把这部分的边缘装饰起来,如图中黄色线部分: 一共需要16根长度为1的荧光棒。

神牛数了好几次结果都不一样,所以他很沮丧,作为哥哥你应该帮帮他。什么,你不想帮?不,你想帮,并且只能使用普通搜索方法,而不能使用广搜或深搜!

输入

第一行,两个整数row,col。 接下来一个row行,col列的矩阵,0表示没有瓷砖,1表示有瓷砖。

对于100%的数据:

1\le row,col \le 1000

输出

一个整数,表示所需的荧光棒数量。

样例

输入

4 4
0 1 0 0
1 1 1 0
0 1 0 0
1 1 0 0

输出

16

输入

1 1
1

输出

4

输入

1 2
1 0

输出

4
时间限制 1000 毫秒
内存限制 128 MB
统计
上一题 下一题