CF1316D Nash Matrix

Nash 设计了一个有趣且简单的棋盘游戏，玩家只需按照当前所站格子上的指令行动即可。 这个棋盘游戏在一个 $n \times n$ 的棋盘上进行。棋盘的行和列编号从 $1$ 到 $n$。第 $r$ 行第 $c$ 列的格子记作 $(r, c)$。 棋盘上的某些格子被称为阻塞区。在每个格子上，都写有以下 $5$ 个字符之一——$U$、$D$、$L$、$R$ 或 $X$——用于指示玩家的行动。假设当前格子为 $(r, c)$，如果字符为 $R$，玩家应向右移动到 $(r, c+1)$；如果为 $L$，则向左移动到 $(r, c-1)$；如果为 $U$，则向上移动到 $(r-1, c)$；如果为 $D$，则向下移动到 $(r+1, c)$。最后，如果格子上的字符为 $X$，则该格子为阻塞区，玩家应停留在该格子（此后游戏对他来说就不再有趣了）。 保证所有字符的设置都不会导致玩家走出棋盘，无论他从哪个格子出发。 玩家从某个格子出发，按照当前格子的指令不断移动，直到进入阻塞区为止。也有可能玩家会无限移动，永远不会进入阻塞区。 你的朋友 Alice 想知道，如果玩家从每一个格子出发，游戏会如何进行。对于棋盘上的每一个起始格子 $(r, c)$，她记录下： - 一个二元组 $(x, y)$，表示如果玩家从 $(r, c)$ 出发，最终会停在 $(x, y)$； - 或者一个二元组 $(-1, -1)$，表示如果玩家从 $(r, c)$ 出发，会一直移动下去，永远不会进入阻塞区。 Alice 可能在骗你，可能不存在满足她所有记录的棋盘。现在给定 Alice 的所有记录，请你判断是否存在这样的棋盘。如果存在，请给出任意一个满足条件的棋盘；如果不存在，输出 INVALID。如果存在多个满足条件的棋盘，你可以输出其中任意一个。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^{3}$），表示棋盘的边长。 接下来的 $n$ 行，每行包含 $2n$ 个整数 $x_1, y_1, x_2, y_2, \dots, x_n, y_n$，其中 $(x_j, y_j)$（$1 \leq x_j \leq n, 1 \leq y_j \leq n$，或 $(x_j, y_j) = (-1, -1)$）是 Alice 为格子 $(i, j)$ 记录的二元组。

如果不存在满足 Alice 所给信息的棋盘，输出一行 INVALID。 否则，第一行输出 VALID。接下来的 $n$ 行，每行输出一个长度为 $n$ 的字符串，表示你找到的一个合法棋盘。每个字符可以是 $U$、$D$、$L$、$R$ 或 $X$。如果存在多个满足条件的棋盘，你可以输出其中任意一个。

对于样例 1： 输出中的棋盘是合法的。 - 如果玩家从 $(1,1)$ 出发，因该格子为 $X$，会停在原地。 - 如果玩家从 $(1,2)$ 出发，按照 $L$ 向左移动，最终停在 $(1,1)$。 - 如果玩家从 $(2,1)$ 出发，按照 $R$ 向右移动，最终停在 $(2,2)$。 - 如果玩家从 $(2,2)$ 出发，因该格子为 $X$，会停在原地。 模拟如下图所示：  对于样例 2： 输出中的棋盘是合法的，除了中心格 $(2,2)$ 外，其他任意格子出发的玩家都会陷入无限循环，永远不会停下。如果从 $(2,2)$ 出发，因该格子为 $X$，会停在原地。 模拟如下图所示：  由 ChatGPT 4.1 翻译