Problem 27695 --E. n皇后摆放问题

27695: E. n皇后摆放问题

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4  Solved: 4
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。在n×n格的棋盘上,已经摆放好其它的一些棋子,皇后与皇后之间如果有棋子,就不能相互攻击,求出在n×n的棋盘上可以摆放最多的相互不能攻击的皇后数。

Input

首先输入nn<=4),然后输入n×n的棋盘,”X”表示已经摆放了的棋子,”.”表示棋盘空位。

Output

输出最多能摆放的皇后数。

Sample Input

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....

Sample Output

4
1
2
2
4

HINT

Source

[Submit][Status]