国际象棋中一只象的价值等于一只车的价值。

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

算法设计:对于给定的设置了堡垒的n×n格棋盘,设计一个随机化算法,在棋盘上放置尽可能多的彼此不受攻击的车.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.接下来的n行中,每行有1个由字符“.”和“X"组成的长度为n的字符串.

结果输出:将计算的在棋盘上可以放置的彼此不受攻击的战车数输出到文件output.txt.