2546: #6068. 「2017 山东一轮集训 Day4」棋盘

给定一个 $n\times n$ 的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置 $(x,y),(u,v)$ 能互相攻击当前仅当满足以下两个条件：

• $x=u$ 或 $y=v$
• 对于 $(x,y)$ 与 $(u,v)$ 之间的所有位置，均不是障碍。

现在有 $q$ 个询问，每个询问给定 ki k_i k​i​​，要求从棋盘中选出 ki k_i k​i​​ 个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？

输入格式

第一行一个整数 $n$。
接下来输入一个 $n\times n$ 的字符矩阵，一个位置若为 .，则表示这是一个空位置，若为 #，则为障碍。
第 $n+2$ 行输入一个整数 $q$ 代表询问个数。
接下来 $q$ 行，每行一个整数 $k$，代表要放的棋子个数。

输出格式

输出共 $q$ 行，每行代表对应询问的最少的互相能攻击到的棋子对数。

样例

样例输入

4
..#.
####
..#.
..#.
1
7

样例输出

2

数据范围与提示

对于 $20\%$ 的数据，$n\le 5$；
对于 $40\%$ 的数据，$n\le 10$；
另外有 $20\%$ 的数据，$q=1$；
对于 $100\%$ 的数据，$n\le 50;q\le 10000;k\le$ 棋盘中空位置数量。