P99553

攻击装置

难度 7 级 二分图
讨论 统计 0通过 0提交 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给定一个 01 矩阵,其中你可以在 0 的位置放置攻击装置。每一个攻击装置 (x,y) 都可以按照“日”字攻击其周围的 8 个位置 (x-1,y-2),(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2),(x-2,y+1),(x+1,y+2),(x+2,y+1)。

求在装置互不攻击的情况下,最多可以放置多少个装置。

输入

第一行一个整数 N,表示矩阵大小为 N \times N。

接下来 N 行每一行一个长度 N 的 01 串,表示矩阵。

输出

一个整数,表示在装置互不攻击的情况下最多可以放置多少个装置。

样例

样例 1
输入
3
010
000
100
输出
4

提示

对于 100\% 的数据,保证 N \le 200。

来源

天津省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交