战车问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在n×n 格的棋盘上放置彼此不受攻击的车。按照国际象棋的规则,车可以攻击与之处在同一行或同一列上的棋子。在棋盘上的若干个格中设置了堡垒,战车无法穿越堡垒攻击别的战车。对于给定的设置了堡垒的n×n格棋盘,设法放置尽可能多彼此不受攻击的车。
对于给定的设置了堡垒的n×n 格棋盘,设计一个概率算法,在棋盘上放置尽可能多彼此不受攻击的车。

Input

输入数据的第一行有1 个正整数n,n≤50。接下来的n行中,每行有1 个由字符’.’和’X’组成的长度为n的字符串。

Output

将计算出的在棋盘上可以放置的彼此不受攻击的战车数输出。

Sample Input

4
....
..X.
.X..
....

Sample Output

6

Hint

Source