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

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

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MB

Description

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

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

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

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

2

数据范围与提示

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

Source/Category