9553 - 攻击装置
时间限制 : 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 串，表示矩阵。
输出
一个整数，表示在装置互不攻击的情况下最多可以放置多少个装置。
样例
输入
3 010 000 100
输出
4
提示
对于 100\% 的数据，保证 N \le 200。
来源
天津省选