[TJOI2013] 攻击装置
题目描述
给定一个 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
输出样例 #1
4
说明
对于 $30\%$ 的数据,保证 $N \le 50$。
对于 $100\%$ 的数据,保证 $N \le 200$。