题目分析

我们需要处理一个动态积雪的网格，支持“清行”“清列”“查询两点间是否能在最大踏雪深度内通行并求最短路”三种操作。核心特点：

• 每小时开始时，所有单元格积雪+1；
• 清行/清列会将对应行/列的积雪重置为0；
• 单元格(r,c)的当前积雪深度 = 当前时间 - max(该行最后清雪时间, 该列最后清雪时间)（因为行/列被清过时，积雪会被重置）。

核心思路

1. 维护清雪时间：用两个数组last_row[r]和last_col[c]分别记录第r行、第c列最后被清雪的时间。
2. 判断单元格可达性：对于任意单元格(r,c)，在当前时间t时，其积雪深度为depth = t - max(last_row[r], last_col[c])。若depth ≤ k（k是当前操作的最大踏雪深度），则该单元格可通行。
3. 最短路分析：
   • 两点(r1,c1)到(r2,c2)的最短路径是曼哈顿距离：|r1-r2| + |c1-c2|（只有走直线时步数最少）。
   • 若直接走曼哈顿路径不可行，需考虑“通过清雪的行/列中转”的情况，但中转路径的步数一定≥曼哈顿距离，因此只需验证直接路径是否可行，或通过起点/终点的行/列中转的路径是否可行。

具体实现

步骤1：维护清雪时间

• 操作1（清行r）：last_row[r] = 当前时间t（注意：每个操作耗时1小时，所以操作执行时的时间是“已完成的操作数”，初始为0，每执行一个操作t+1）。
• 操作2（清列c）：last_col[c] = 当前时间t。

步骤2：处理查询操作（操作3）

对于查询(r1,c1) → (r2,c2), k：

1. 先计算当前时间t（即当前是第t个操作，初始为0，每执行一个操作t加1）。
2. 验证直接路径是否可行：
   • 检查起点(r1,c1)、终点(r2,c2)是否可达（depth ≤ k）。
   • 检查路径上所有单元格的可达性：由于直接路径是“先走到同一行/列，再走到终点”，只需验证起点的行/列是否可达、终点的行/列是否可达（因为路径上的单元格的积雪深度不会超过起点/终点的行/列的积雪深度）。
3. 若直接路径不可行，验证中转路径：
   • 中转方式1：从起点走到其所在行r1的某个可达单元格，再走到终点的行r2/列c2（需验证r1行、r2行/c2列是否可达）。
   • 中转方式2：从起点走到其所在列c1的某个可达单元格，再走到终点的行r2/列c2（需验证c1列、r2行/c2列是否可达）。
4. 若以上任意一种路径可行，取步数最少的（即曼哈顿距离）；否则输出-1。

关键优化

由于n,m可达1e6，q可达3e5，不能遍历路径上的所有单元格，需利用“行/列的清雪时间”快速判断路径可行性：

• 对于直接路径，只需验证：
  • 起点(r1,c1)可达：t - max(last_row[r1], last_col[c1]) ≤ k。
  • 终点(r2,c2)可达：t - max(last_row[r2], last_col[c2]) ≤ k。
  • 路径上的行/列可达：t - last_row[r1] ≤ k（起点行的积雪深度）且t - last_col[c2] ≤ k（终点列的积雪深度），或t - last_col[c1] ≤ k（起点列的积雪深度）且t - last_row[r2] ≤ k（终点行的积雪深度）。

代码示例

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    n = int(data[ptr])
    ptr +=1
    m = int(data[ptr])
    ptr +=1
    q = int(data[ptr])
    ptr +=1
    
    last_row = [0]*(n+2)  # 行1~n
    last_col = [0]*(m+2)  # 列1~m
    t = 0  # 当前时间（操作数）
    
    for _ in range(q):
        op = int(data[ptr])
        ptr +=1
        if op == 1:
            # 清行r
            r = int(data[ptr])
            ptr +=1
            last_row[r] = t
        elif op == 2:
            # 清列c
            c = int(data[ptr])
            ptr +=1
            last_col[c] = t
        else:
            # 查询：r1 c1 r2 c2 k
            r1 = int(data[ptr]); ptr +=1
            c1 = int(data[ptr]); ptr +=1
            r2 = int(data[ptr]); ptr +=1
            c2 = int(data[ptr]); ptr +=1
            k = int(data[ptr]); ptr +=1
            
            # 计算起点、终点的积雪深度
            d1 = t - max(last_row[r1], last_col[c1])
            d2 = t - max(last_row[r2], last_col[c2])
            if d1 > k or d2 > k:
                print(-1)
                t +=1
                continue
            
            # 检查直接路径是否可行：两种走法（先同行再同列，或先同列再同行）
            # 走法1：(r1,c1) → (r1,c2) → (r2,c2)
            valid1 = (t - max(last_row[r1], last_col[c2]) <= k)
            # 走法2：(r1,c1) → (r2,c1) → (r2,c2)
            valid2 = (t - max(last_row[r2], last_col[c1]) <= k)
            
            if valid1 or valid2:
                print(abs(r1 - r2) + abs(c1 - c2))
            else:
                # 检查中转路径：通过起点行/列 或 终点行/列
                # 中转1：起点行r1 + 终点行r2
                valid3 = (t - last_row[r1] <= k) and (t - last_row[r2] <= k)
                # 中转2：起点列c1 + 终点列c2
                valid4 = (t - last_col[c1] <= k) and (t - last_col[c2] <= k)
                # 中转3：起点行r1 + 终点列c2（其实就是走法1，已判断）
                # 中转4：起点列c1 + 终点行r2（其实就是走法2，已判断）
                if valid3 or valid4:
                    # 中转路径的步数：|r1-r2| + |c1-c2|（同曼哈顿）
                    print(abs(r1 - r2) + abs(c1 - c2))
                else:
                    print(-1)
        t +=1  # 每个操作耗时1小时，时间+1

if __name__ == "__main__":
    main()

复杂度分析

• 时间复杂度：每个操作（包括查询）的处理时间为$O(1)$，总复杂度$O(q)$，可处理$3e5$次操作。
• 空间复杂度：维护两个数组last_row和last_col，空间复杂度$O(n+m)$，可处理$1e6$规模的网格。