[TJOI2013]攻击装置
题号：NC20446
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个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*N。
接下来N行每一行一个长度N的01串，表示矩阵。

输出描述:

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

输入

复制 
3
010
000
100

输出

复制 
4

备注:

30%数据
100%数据