F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 3175. -- [Tjoi2013]攻击装置

3175: [Tjoi2013]攻击装置

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1706  Solved: 801
[Submit][Status][Discuss]

Description

给定一个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)
求在装置互不攻击的情况下,最多可以放置多少个装置。

Input

第一行一个整数N,表示矩阵大小为N*N。接下来N行每一行一个长度N的01串,表示矩阵。

Output

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

Sample Input

3
010
000
100

Sample Output

4

HINT

100%数据 N<=200

Source

[Submit][Status][Discuss]

HOME Back