CF1185E Polycarp and Snakes

经过一周的辛勤工作后，Polycarp 喜欢娱乐一下。他最喜欢的娱乐方式是画蛇。他会拿出一张 $n \times m$ 的矩形方格纸（$n$ 表示行数，$m$ 表示列数），然后开始在格子里画蛇。 Polycarp 用小写拉丁字母画蛇。他总是用符号 'a' 画第一条蛇，用符号 'b' 画第二条蛇，用符号 'c' 画第三条蛇，依此类推。每条蛇都有自己独特的符号。由于拉丁字母只有 $26$ 个，Polycarp 非常疲惫，不想发明新符号，所以画蛇的总数不会超过 $26$ 条。 由于一周快结束时 Polycarp 很累，他画蛇时只画直线，不拐弯。因此，每条蛇要么是竖直的，要么是水平的。每条蛇的宽度都是 $1$，也就是说，每条蛇的尺寸要么是 $1 \times l$，要么是 $l \times 1$，其中 $l$ 是蛇的长度。注意，蛇不能拐弯。 当 Polycarp 画新蛇时，可以使用已经被占用的格子。在这种情况下，他会“覆盖”之前的内容，将蛇画在上面，覆盖原有的符号。 最近 Polycarp 在工作时发现了一张写有拉丁字母的方格纸。他想知道，是否有可能按照上述规则，从一张空白纸画出这张纸上的内容。如果可能，他还想知道一种画蛇的方式。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示需要解决的测试用例数。接下来是 $t$ 个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2000$），分别表示方格纸的行数和列数。 接下来的 $n$ 行，每行包含 $m$ 个字符，表示方格纸对应格子的内容。每个格子要么是小写拉丁字母，要么是点号（'.'），点号表示空格。 保证每个测试用例中所有方格纸的总面积不超过 $4 \cdot 10^6$。

对于输入中的每个测试用例，输出一行答案。 如果可以通过画蛇得到输入的方格纸，输出 YES，否则输出 NO。 如果答案为 YES，则在下一行输出一个整数 $k$（$0 \le k \le 26$），表示蛇的数量。接下来输出 $k$ 行，每行四个整数 $r_{1,i}$、$c_{1,i}$、$r_{2,i}$、$c_{2,i}$，表示第 $i$ 条蛇的两个端点坐标（$1 \le r_{1,i}, r_{2,i} \le n$，$1 \le c_{1,i}, c_{2,i} \le m$）。蛇的输出顺序应与画蛇的顺序一致。如果有多种方案，可以输出任意一种。 注意，Polycarp 总是从一张空白纸开始画蛇。

由 ChatGPT 4.1 翻译