Description

给定一个 $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$。

实现细节

你需要实现如下函数：

int32 [][] calculate_moves(int32 [][] A, int32 K)

• $A$：长度为 $N$ 的数组，每个元素为长度为 $M$ 的数组，描述了棋盘。
• $K$：移动限制参数。
• 该函数应返回长度为 $N$ 的数组，每个元素为长度为 $M$ 的数组，表示每个单元格最少需要多少步可到达，无法到达的单元格对应值为 $-1$。

Input Format

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]

Output Format

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]

其中，$R$ 为你实现的 calculate_moves 返回的结果数组。

Hint

输入输出样例

样例 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$ 恰好出现一次。

由 ChatGPT 5 翻译