空城计
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
虚者虚之,疑中生疑。刚柔之际,奇而复奇。
题目描述
33DAI 拿到了一张猫猫国地图,这张地图是一个 行 列的字符画。
用 #
表示城市的分界线,用 @
表示守军,用 .
表示没有守军的地块。
其中第一行、最后一行、第一列、最后一列都保证是 #
。所有上下左右相邻的 #
为连续的分界线,这样就把整个地图分成了若干城市(每个城市至少有一个 @
或者一个 .
)。每个城市中都可能有或没有守军。
33DAI 想要先分析一下猫猫国共有多少个城市。
然后 33DAI 定义城市的守城率为“@
的数量”除以“@
和 .
的数量之和”。请输出守城率最低的城市的守军数量(即 @
的数量,如果有多个城市守城率并列最低,输出守军最少的那个数量)。
输入格式
第一行一个数 。
接下来 行为 行 列的字符画,即地图。
输出格式
两个整数,城市数量及守城率最低的城市的守军数量。
8
########
#......#
##.....#
##..####
####...#
##.....#
#...@@.#
########
1 2
看上去有两个城市,但是实际上只有上下左右相邻的分界线才连在了一起,中间是没有脸上的,所以只有一个城市,有两名守军。
8
########
#..@..@#
#..@..@#
#..@..@#
########
#....@@#
#....@@#
########
2 4
显然两个城市,守城率相同(都是 )。输出守军数量较少的那个守军数量。
7
#######
#.#.#.#
#######
#.#.#.#
#######
#.#.#.#
#######
9 0
全是空城
9
#########
#@#@#@#@#
#########
#@#@#@#@#
#########
#@#@#@#@#
#########
#@#@#@#@#
#########
16 1
全都有一个守军。
数据规模与约定
对于 的数据,。
- 子任务 1(10 分):保证 。
- 子任务 2(20 分):保证只有一个城市。
- 子任务 2(30 分):保证全是空城(没有字符
@
)。 - 子任务 2(40 分):没有特殊限制。