P14036 [PAIO 2025] Rooks

**DO NOT** include `rooks.h`. Submit using C++ >=17.

给定一个 $N \times M$ 的矩阵 $A$，矩阵中的每个元素从 $1$ 到 $N \times M$ 恰好出现一次。现在有一个车（rook），它正位于矩阵中值为 $1$ 的单元格所在的位置。此外，还给定一个整数 $K$。 该车可以从单元格 $(r,c)$ 跳到单元格 $(r',c')$，当且仅当同时满足下列所有条件： * $(r,c) \neq (r',c')$，即必须移动到不同的单元格； * 要么 $r=r'$，要么 $c=c'$，即只能在同一行或同一列中移动； * $0 < A[r'][c'] - A[r][c] \leq K$。 请为矩阵中的每个单元格求出该车从值为 $1$ 的单元格出发最少需要多少步可以到达，若无法到达则返回 $-1$。 ### 实现细节 你需要实现如下函数： ``` vector calculate_moves(vector A, int K) ``` * $A$：长度为 $N$ 的数组，每个元素为长度为 $M$ 的数组，描述了棋盘。 * $K$：移动限制参数。 * 该函数应返回长度为 $N$ 的数组，每个元素为长度为 $M$ 的数组，表示每个单元格最少需要多少步可到达，无法到达的单元格对应值为 $-1$。

``` N M K A[0][0] A[0][1] ... A[0][M-1] A[1][0] A[1][1] ... A[1][M-1] . . . A[N-1][0] A[N-1][1] ... A[N-1][M-1] ```

``` R[0][0] R[0][1] ... R[0][M-1] R[1][0] R[1][1] ... R[1][M-1] . . . R[N-1][0] R[N-1][1] ... R[N-1][M-1] ``` 其中，$R$ 为你实现的 `calculate_moves` 返回的结果数组。

## 输入输出样例 ### 样例 1 考虑如下调用： ``` calculate_moves( [[8, 2, 4, 20, 5], [14, 13, 1, 19, 7], [15, 18, 12, 6, 11], [10, 9, 3, 16, 17]]) ``` 这里 $N=4, M=5, K=5$。 包含 $1$ 的单元格是 $A[1][2]$，因此在你返回的数组 $R$ 中，$R[1][2]=0$，因为起点无需移动。 到达 $A[3][0]=10$，可以从 $A[1][2]=1$ 走到 $A[0][2]=4$（同一列，且 $4-1=3 \leq 5$），再从 $A[0][2]=4$ 走到 $A[0][0]=8$（同一行，$8-4=4\leq5$），最后从 $A[0][0]=8$ 走到 $A[3][0]=10$（同一列，$10-8=2$）。因此 $R[3][0]=3$。 注意无法到达 $A[0][1]=2$，因此 $R[0][1]=-1$。 函数返回结果如下： ``` [[2, -1, 1, 6, 2], [4, -1, 0, 5, 3], [4, 5, 5, -1, 4], [3, -1, 1, -1, -1]] ``` ## 评分器样例 ### 输入格式 ``` N M K A[0][0] A[0][1] \cdots A[0][M-1] A[1][0] A[1][1] \cdots A[1][M-1] \vdots A[N-1][0] A[N-1][1] \cdots A[N-1][M-1] ``` ### 输出格式 ``` R[0][0] R[0][1] \cdots R[0][M-1] R[1][0] R[1][1] \cdots R[1][M-1] \vdots R[N-1][0] R[N-1][1] \cdots R[N-1][M-1] ``` # 数据范围与子任务 * $1 \leq N, M \leq 2500$ * $1 \leq K \leq N \cdot M$ * $1 \leq A[i][j] \leq N \cdot M$ * $A$ 中每个整数 $1$ 到 $N \cdot M$ 恰好出现一次。 | 子任务 | 分值 | 其他约束 | | :------ | :---- | :--------------------- | | 1 | 9 | $N=1$ | | 2 | 15 | $N,M \leq 100$ | | 3 | 11 | $K=1$ | | 4 | 19 | $K=N \cdot M$ | | 5 | 15 | $N,M \leq 500$ | | 6 | 31 | 无进一步约束。 | 由 ChatGPT 5 翻译