阵地扩张
题目描述
背景设定
2025年的某个摸鱼的下午，你又一次刷到了前篇一律的穿越剧。你不耐烦的划向下一个短剧，但是这时耳边响起了一阵阵AI的声音：“恭喜宿主成功被选中成为穿越者，距离穿越还有30秒”。
“什么！”
系统提醒您：“作为穿越者，你的任务是在给定的这片战场平定叛乱”。
战场符号说明
给你一个 n 行 m 列的战场，以下为符号类型说明：
| 符号 | 含义 | 详细说明 |
|---|---|---|
. |
平地 | 可行军，可被我方征服，无特殊效果 |
! |
我方初始阵地 | 开始时（第0秒），征服该地区并建立阵地，之后每秒会征服上、下、左、右四个方向的位置，并在征服的位置建立阵地。（注：每个测试用例至少有一个!。已经征服的位置将不会重复访问） |
# |
山丘 | 我们没有配备梯子，将无法到达。 |
@ |
叛军阵地 | 如果某一时刻我方征服该地区，则当前秒数的攻破阵地数将会增加1。 |
问题类型
程序需要处理两种询问：
-
征服指定位置的时间
- 输入格式：
1 x y - 输出要求：征服位置
(x, y)所需的秒数。如果无法征服（如被山丘阻挡或无法到达），则输出-1。
- 输入格式：
-
到指定秒数攻破的敌方阵地数量
- 输入格式：
2 r - 输出要求：从开始到第
r秒（含）共计攻破的敌方阵地数量。 （不保证r小于等于征服完毕所需的总时间）
- 输入格式：
输入描述
第一行包含三个整数 n，m，q（1 ≤ n, m ≤ 2×10³，1 ≤ q ≤ 2×10⁵）。
随后 n 行，每行是一个长度为 m 的字符串，表示战场地图。
接着有 q 次询问，每行询问的格式为以下两种之一：
- 1 x y（1 ≤ x ≤ n，1 ≤ y ≤ m）
- 2 r（0 ≤ r ≤ n×m）
输出描述
对于每次询问，输出其对应的结果（每个结果占一行）。
Samples
3 3 3
@ . .
. ! .
. . #
1 2 2
1 1 3
2 2
0
2
1
3 3 1
! . .
. . .
. . !
1 2 3
1
3 5 3
@ @ @ # .
@ ! @ # .
@ @ @ # .
2 0
2 1
1 1 4
0
4
-1
注意：本体数据量较大，建议使用快速的输入方式。
Limitation
2s, 1024KiB for each test case.