#214167. [PAIO 2025] Rooks

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

You are given an matrix where each element from to appears exactly once. You are given a rook that is on the cell that contains the element with value . You are also given a .

The rook can jump from a cell to a cell if both of the following conditions hold:

• , so we have to move to a different cell,
• either or , so we move only in one row or one column,
• .

Find for each cell of the matrix the minimum number of moves it takes the rook to reach it from the cell containing , or if it is not reachable at all.

Implementation Details

You need to implement the following function:

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

• : array of length of arrays of length describing the board.
• : the movement constraint.
• The function should return an array of length of arrays of length containing the minimum number of moves needed to reach that cell from cell . If a cell is unreachable, the value for that cell should be equal to .

Examples

Example 1

Consider the following call:

calculate_moves(
    [[8, 2, 4, 20, 5],
     [14, 13, 1, 19, 7],
     [15, 18, 12, 6, 11],
     [10, 9, 3, 16, 17]])

We have .

The cell containing , which we start from, is . Therefore in the array returned by calculate_moves, value should be equal to , as we don't need to make any moves to reach that cell.

To reach , we can go from to (as they are in the same column, and ), then from to (as they are in the same row, and ), then finally from to (as they are in the same column and ). Therefore in the array , value should be equal to .

Notice that it is not possible to reach in any way, so the value should be equal to .

The procedure should return:

[[2, -1, 1, 6, 2],
 [4, -1, 0, 5, 3],
 [4, 5, 5, -1, 4],
 [3, -1, 1, -1, -1]]

Sample Grader

Input format:

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]

Output format:

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]

Here, is the array returned by calculate_moves.

Constraints

• Each integer from to appears in exactly once.

Subtasks