#3175. [Tjoi2013]攻击装置

[Tjoi2013]攻击装置

题目描述

给定一个 01 矩阵,其中你可以在 0 的位置放置攻击装置。每一个攻击装置 (x,y)(x,y) 都可以按照「日」字攻击其周围的 88 个位置$(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)$。

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

输入格式

第一行一个整数 nn,表示矩阵大小为 n×nn\times n。接下来 nn 行每一行一个长度 nn01 串,表示矩阵。

输出格式

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

样例输入

3
010
000
100

样例输出

4

数据规模与提示

对于 100%100\% 的数据,n200n\le 200