#459. [CZOI2022 F] 迷宫探险

    ID: 459 传统题 1000ms 256MiB 尝试: 29 已通过: 3 普及/提高- 上传者: 标签>来源常州小学生市赛时间2022搜索DFSBFS

[CZOI2022 F] 迷宫探险

题目描述

完成了俱乐部老师布置的命题任务,小 X 决定和朋友们玩一款探险类游戏放松一下心情。这个游戏的场景是在一个地下迷宫中,这个迷宫由 N×NN\times N 的网格构成,小X和他的朋友们每人占据一个格子,他们每人带领一支探险队。每一分钟小 X 会让他的探险队员从上下左右四个方向前往相邻的格子(只要相邻的格子不是障碍物),同时他的朋友们也会跟小 X 一样做相同的操作。迷宫中有些格子是空的,而有些格子有自动计分器,最早到达这个格子的队员所属的玩家会得到 11 分,然后这个自动计分器会消失,即之后到达这个格子就不会获得分数,如果有多个玩家的队员同时到达有自动计分器的格子,那么这些玩家都能得到 11 分。现在小 X 想知道得分最多的玩家得到了多少分,以及所有玩家一共得到了多少分。你可以认为每位玩家的手下都有足够多的探险队员。

输入格式

第一行一个整数 N N,表示地下迷宫的大小。

接下来 NN 行,每行 NN 个字符,. 表示这个格子是个空地,# 表示这个格子是个障碍物,@ 表示开始时有玩家在这个格子,$ 表示这个格子有自动计分器。除了障碍物所在格子,所有格子均可通行。

输出格式

输出数据共有两行,每行一个整数,第一行的整数表示得分最多的玩家得到了多少分,第二行的整数表示所有的玩家一共得到了多少分。

3 10
@$#
#$#
#$@
2 4

样例解释

在第一分钟,位于 (1,1)(1,1) 的玩家派出的探险队员到达 (1,2)(1,2) 得到 11 分,位于 (3,3)(3,3) 的玩家派出的探险队员到达 (3,2)(3,2) 得到 11 分。在第二分钟,两位玩家派出的探险队员同时到达 (2,2)(2,2),各得 11 分,之后即使游戏再进行下去也没有意义了,因为他们不可能再得到任何分数。得分最多的玩家得到的分数为 22 分,所有玩家一共得到了 44 分。

数据范围

测试点编号 NN 特殊性质
11 10\le 10 只有一个玩家
22 只有一个得分点
353\sim 5
686\sim 8 50\le 50
9109 \sim 10 100\le 100

1玩家的数量101 \le 玩家的数量 \le 10