P12560 [UTS 2024] Randomized Palindromes

给定一个由 0 和 1 组成的 $n \times n$ 二进制矩阵。初始时，你有一个空字符串 $S$。你从位置 $(0,0)$（左上角）出发，每次只能向右或向下移动。将经过的每个元素按顺序添加到字符串 $S$ 中。 判断是否存在一条路径使得 $S$ 成为回文串。如果存在，输出这样的路径；否则输出不存在。 注意每个矩阵都是随机生成的。

第一行包含一个整数 $n$ $(1 \le n \le 5\,000)$ —— 矩阵的大小。 接下来的 $n$ 行，每行包含 $n$ 个字符 $a_{i,j}$ $(0 \le a_{i,j} \le 1)$ —— 描述矩阵的内容。 输入矩阵是从所有可能的 $n \times n$ 有效矩阵中随机选取的。

如果不存在这样的回文路径，输出一行 $\tt{NO}$。 否则，第一行输出 $\tt{YES}$。接下来的 $2n-1$ 行，每行输出两个整数 $x_i$ 和 $y_i$ ($0 \leq x_i, y_i < n$) —— 表示路径上第 $i$ 个单元格的坐标。

- （$5$ 分）：$n \le 10$； - （$9$ 分）：$n \le 100$； - （$19$ 分）：$n \le 500$； - （$27$ 分）：$n \le 1\,500$； - （$40$ 分）：无额外限制。 翻译由 DeepSeek V3 完成