2901:国际象棋

时间限制:2 S   /  内存限制:65536 KB
AC:10   /  Submit:20
问题描述

在国际象棋中,“车”是一种可以上下或者左右方向移动的棋子。棋盘上面有一些墙,可以阻止墙两侧同一行或者同一列的两个“车”互相攻击。现在要求在棋盘上放置尽可能多的车(不能放在墙上),必须保证任意两个“车”之间都不能互相攻击到。

输入描述

一个正整数T,表示案例的数量。(T<=10)

每组案例先是一个正整数n,表示棋盘的大小是n*n。(n<=4)

然后是n行n列字符,每个字符要么是'.'表示棋盘,要么是'X'表示墙。

输出描述

针对每组案例,输出一个整数,表示棋盘上最多可以放置的“车”的数量。

每组案例输出完要换行。

样例输入复制样例

2

4

.X..

....

XX..

....

2

XX

.X

样例输出

5

1

相关

厦大附中线上赛(2020/8/16)


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1