同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2088_AL094战车问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 43| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504315018000-Problem List-采集的数据-后羿采集器.html

Pro.ID

2088

Title

AL094 战车问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2088

AC

Submit

Ratio

0.00%

时间&空间限制

Time Limit: 1200/400 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

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

输入

输入第一行是一个正整数n ( 3 < n < 49 )。接下来的n行中，每行有一个由字符 '.'和 'X' 组成的长度为n的字符串。

输出

Description

Input

输入第一行是一个正整数n ( 3 < n < 49 )。接下来的n行中，每行有一个由字符 '.'和 'X' 组成的长度为n的字符串。

Output

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

Sample Input

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

Sample Output

样例输入