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

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

2

数据范围与提示

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