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

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

给定一个 $ 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 $ 行，每行代表对应询问的最少的互相能攻击到的棋子对数。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出