徐老师的传送门plus
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
众所周知徐老师很喜欢玩一款名为 《传送门》 的游戏，在游戏中，玩家会获得一把传送枪，在任意位置可以打出传送门，当打出两个传送门时，这两个传送门将会连通，以此来完成一些任务或者穿越一些障碍
而这个游戏最近出了一个新的模式——定点传送模式
在这个模式下，玩家将会进入到一个 $n * m$ 的迷宫中，这个迷宫共有 $n * m$ 个房间，并且房间之间完全堵死，无法同行
在这些迷宫中，将会存在 $k$ 个地点拥有传送门，并且在这个模式下，将会有三种特殊的传送门用编号 $A,B,C$ 表示
若 $(x,y)$ 这个房间的是 $A$ 类传送门，则可以传送到周围一圈的房间，即 $(上，下，左，右，左上，右上，左下，右下)$
若 $(x,y)$ 这个房间的是 $B$ 类传送门，则可以传送到 $(x,i)$ 房间，其中 $1 \leq i \leq m$
若 $(x,y)$ 这个房间的是 $C$ 类传送门，则可以传送到 $(i,y)$ 房间，其中 $1 \leq i \leq n$
注意，所有的传送门均是单向传送
现在徐老师想知道，如果他可以任选一个房间作为起点，他最多可以使用多少个传送门？
这里我们认为：一个传送门可以重复使用，一个房间可以重复到达，但是重复使用同一个传送门只计算一次答案
输入格式
输入第一行包含三个整数 $n,m,k$ 表示地图大小及传送门数量接下来 $k$ 行，每行用形如 $x_i,y_i,z_i$ 的形式表示一个传送门在 $(x_i,y_i)$ 处，种类为 $z_i \in [A,B,C]$
|数据点|$n,m$|$k$|
|:---:|:---:|:---:|
|$1$|$n=m=20$|$k=16$|
|$2$|$n=m=1000$|$k=300$|
|$3$|$n=m=10^5$|$k=500$|
|$4$|$n=m=5000$|$k=2500$|
|$5$|$n=m=5000$|$k=50000$|
|$6$|$n=m=10^6$|$k=50000$|
|$7$|$n=m=10^6$|$k=80000$|
|$8 \sim 10$|$n=m=10^6$|$k=10^5$|
对于所有的数据保证同一个地点不会有多个传送门
输出格式
输出一个数字表示徐老师最多能使用的传送门数量样例
7 7 10
2 2 B
2 4 C
1 7 C
2 7 A
4 2 C
4 4 B
6 7 A
7 7 B
7 5 C
5 2 B923CSP-S秋季提高组模拟赛(2)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-9-17 16:30
- 结束于
- 2023-9-27 16:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 16
