社区讨论

翻译

CF1185EPolycarp and Snakes参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi7z3blz
此快照首次捕获于
2025/11/21 05:58
4 个月前
此快照最后确认于
2025/11/21 05:58
4 个月前
查看原帖

题目描述

经过一周的艰苦工作,Polycarp喜欢玩得很开心。Polycarp最喜欢的娱乐是画蛇。他拿了一张大小为 n×mn\times m 的矩形方格纸(其中n是行数,m是列数),开始在细胞中画蛇。
Polycarp用小写拉丁字母"a"~"z"绘制第1~26条蛇。Polycarp很累,他不想发明新的符号,所以画蛇的总数不超过26条。
由于到本周末,Polycarp已经很累了,他把蛇画成没有弯曲的直线。所以每条蛇都是垂直或水平放置的。任何一条蛇的宽度等于1,即每条蛇的大小是 1×l1\times l​l×1l\times 1​ ,其中l是蛇的长度。
当Polycarp画出一条新的蛇时,他可以使用已经被占据的细胞来画蛇。在这种情况下,他会覆盖单元格中以前的值。
最近,当Polycarp工作时,他发现了一张有拉丁字母的方格纸。他想知道是否可以根据上面描述的规则,从一张空纸上画一些蛇来得到这张纸。如果可能的话,他对画蛇的方法很感兴趣。

输入格式

输入的第一行包含一个整数 t(1t105)t\left(1\le t \le 10^5 \right) ——测试数据组数。
测试数据第一行包含两个整数 n,m(1n,m2000)n,m\left(1 \le n, m \le 2000\right) ——方格纸的长度和宽度。
接下来的n行测试数据描述包含m个符号,这些符号负责工作表上相应单元格的内容。它可以是小写拉丁字母或符号点(“.”,代表空单元格)。
保证每个数据中所有方格纸的总面积不超过 41064\cdot10^6 ​

输出格式

在测试数据输出的第一行中,如果可以绘制蛇,请打印“YES”,以便从输入中获取一张纸。如果不可能,请打印"NO"。
如果此问题的答案是肯定的,那么请按以下格式打印绘制蛇的方法。在下一行中,打印一个整数k(0k26)k\left(0\le k\le 26\right)——蛇的数量。然后打印k行,每行打印四个整数r1,i,c1,i,r2,i,c2,ir_{1,i},c_{1,i},r_{2,i},c_{2,i}——第i条蛇的端点坐标(1r1,i,r2,in,1c1,i,c2,im)( 1 \le r_{1,i}, r_{2,i} \le n, 1 \le c_{1,i}, c_{2,i} \le m )。蛇应该按画的顺序印刷。如果有多个解决方案,您可以打印其中任何一个。
注意,Polycarp从一张空纸开始画蛇。

回复

5 条回复,欢迎继续交流。

正在加载回复...