Problem D: 火力网

Problem D: 火力网

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 295  Solved: 104
[Submit][Status][Web Board]

Description

给你张N*N的地图,地图上有墙,用"X"表示,有空地,用” . "表示。空地上可以放兵,每个兵可以攻击他的上下左右四条直线范围(不能穿墙) 
问在防止互相误伤的前提(任何一个兵不在其他兵射程之内),最多摆放多少个兵。 

Input

第一行给出一个数字n
以下n行是N*N的地图(0<=n<=8)

Output

对应每组数据最多能放多少兵,每组数据占一行。

Sample Input

4
.X..
....
XX..
....

Sample Output

5

HINT

[Submit][Status]