3949: 空城计(挖土机 CSP-J 模拟赛 ~ 第十四场)

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

33DAI 拿到了一张猫猫国地图，这张地图是一个 � 行 � 列的字符画。

用 # 表示城市的分界线，用 @ 表示守军，用 . 表示没有守军的地块。

其中第一行、最后一行、第一列、最后一列都保证是 #。所有上下左右相邻的 # 为连续的分界线，这样就把整个地图分成了若干城市（每个城市至少有一个 @ 或者一个 .）。每个城市中都可能有或没有守军。

33DAI 想要先分析一下猫猫国共有多少个城市。

然后 33DAI 定义城市的守城率为“@ 的数量”除以“@ 和 . 的数量之和”。请输出守城率最低的城市的守军数量（即 @ 的数量，如果有多个城市守城率并列最低，输出守军最少的那个数量）。

输入

第一行一个数 �。

接下来 � 行为 � 行 � 列的字符画，即地图。

输出

两个整数，城市数量及守城率最低的城市的守军数量。

样例输入 复制 

8
########
#......#
##.....#
##..####
####...#
##.....#
#...@@.#
########

样例输出 复制 

1 2

提示

输入数据1： 

8
########
#......#
##.....#
##..####
####...#
##.....#
#...@@.#
########

输出数据1： 

1 2
看上去有两个城市，但是实际上只有上下左右相邻的分界线才连在了一起，中间是没有脸上的，所以只有一个城市，有两名守军。

输入数据2： 

8
########
#..@..@#
#..@..@#
#..@..@#
########
#....@@#
#....@@#
########

输出数据2： 

2 4
显然两个城市，守城率相同（都是 13）。输出守军数量较少的那个守军数量。

输入数据3： 

7
#######
#.#.#.#
#######
#.#.#.#
#######
#.#.#.#
#######

输出数据3：

9 0

全是空城

输入数据4： 

9
#########
#@#@#@#@#
#########
#@#@#@#@#
#########
#@#@#@#@#
#########
#@#@#@#@#
#########

输出数据4： 

16 1

全都有一个守军。

数据规模与约定

对于 100% 的数据，1≤�≤500。

  • 子任务 1（10 分）：保证 �=3。
  • 子任务 2（20 分）：保证只有一个城市。
  • 子任务 2（30 分）：保证全是空城（没有字符 @）。
  • 子任务 2（40 分）：没有特殊限制。

来源/分类

提交提交记录统计露一手!