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

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

题目描述

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

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

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

输入格式

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

输出格式

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

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

数据范围与提示

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