#P14916. [UTS2024] Randomized Palindromes

    ID: 14132 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>CF2500动态规划概率论构造字符串贪心双向搜索

[UTS2024] Randomized Palindromes

题目描述

给定一个由 00 和 11 组成的 n×nn \times n 二进制矩阵。初始时,你有一个空字符串 SS。

你从位置 (0,0)(0,0),即左上角开始,每一步只能向右或向下移动。你会按照经过格子的顺序,将每个经过格子的元素依次追加到字符串 SS 中。

请判断是否存在一种走法,使得最终得到的 SS 是一个回文串。如果存在,请输出达到这一目标的路径。

注意:本题中的每个矩阵都是随机生成的。

输入格式

第一行包含唯一的整数 nn,表示矩阵大小。

接下来 nn 行,每行包含 nn 个字符 ai,ja_{i,j},表示矩阵内容。

输入矩阵是在所有合法的 n×nn \times n 二进制矩阵中随机选取的。

输出格式

如果不存在这样的回文路径,输出 NO。

否则,第一行输出 YES。接下来 2n−12n-1 行,每行输出两个整数 xix_i 和 yiy_i,表示第 ii 个经过的格子的坐标。

坐标满足 0≤xi,yi<n0 \le x_i,y_i < n。

输入

2
01
00

输出

YES
0 0
0 1
1 1

数据范围

1≤n≤50001 \le n \le 5000

0≤ai,j≤10 \le a_{i,j} \le 1

评分方式

  1. 55 分:n≤10n \le 10;
  2. 99 分:n≤100n \le 100;
  3. 1919 分:n≤500n \le 500;
  4. 2727 分:n≤1500n \le 1500;
  5. 4040 分:无额外限制。