BZPRO
#4930. 棋盘
内存限制：512 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
给定一个n×n的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置(x,y),(u,v)能互相攻击当前仅
当满足以下两个条件：
1:x=u或y=v
2:对于(x,y)与(u,v)之间的所有位置，均不是障碍。
现在有q个询问，每个询问给定ki，要求从棋盘中选出ki个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？
输入格式
第一行一个整数n。
接下来输入一个n×n的字符矩阵，一个位置若为.，则表示这是一个空位置，若为#，则为障碍。
第n+2行输入一个整数q代表询问个数。
接下来q行，每行一个整数k，代表要放的棋子个数。
n ≤ 50, q ≤ 10000, k ≤ 棋盘中空位置数量
输出格式
输出共q行，每行代表对应询问的最少的互相能攻击到的棋子对数。
样例
样例输入
4
..#.
####
..#.
..#.
1 7
样例输出
2
数据范围与提示
BZPRO