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

传统 1000 ms 512 MiB

$160$ 通过 $307$ 提交

题目描述

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

1. $x = u$ 或 $y = v$
2. 对于 $(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$ 棋盘中空位置数量。