风云 (Risk) - 题目

Risk 是一款在世界地图上进行的棋盘游戏。地图被边界划分为若干个区域。每个区域由一名玩家（你或你的对手之一）控制。你控制的任何区域都包含正数个你的军队。

在每个回合中，你可以移动你的军队。你的每支军队既可以留在原地，也可以从一个区域移动到与其相邻且由你控制的区域。这些移动是一个接一个进行的，顺序由你选择。在任何时候，每个区域都必须包含至少一支军队。

出于战略目的，将你的军队移动到与对手区域相邻的区域，并尽量减少完全被你控制的其他区域包围的区域上的军队数量，是非常重要的。你希望你最薄弱的环节——即军队数量最少的边界区域（与对手区域相邻的由你控制的区域）——尽可能强大。在一轮移动后，最薄弱的边界区域上的军队数量最大可以是多少？

第一行包含一个正整数：测试用例的数量，最多为 100。对于每个测试用例：

一行包含一个整数 $n$ ($1 \le n \le 100$)：区域的数量。
一行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 100$)：你在每个区域上的军队数量。数值 0 表示该区域由你的对手控制，而正数表示该区域由你控制。
$n$ 行，每行包含 $n$ 个字符，每个字符为 'Y' 或 'N'。如果区域 $i$ 和区域 $j$ 相邻，则第 $j$ 行的第 $i$ 个字符为 'Y'，否则为 'N'。这种邻接关系是对称的，且第 $i$ 行的第 $i$ 个字符始终为 'N'。

在每个测试用例中，你至少控制一个区域，且你的对手至少控制一个区域。此外，你控制的区域中至少有一个与你对手控制的至少一个区域相邻。

对于每个测试用例：

2
3
1 1 0
NYN
YNY
NYN
7
7 3 3 2 0 0 5
NYNNNNN
YNYYNNN
NYNYYNN
NYYNYNN
NNYYNNN
NNNNNNY
NNNNNYN

1
4

QOJ.ac