#P18570. [ukiepc2026]Kilt Quilt
[ukiepc2026]Kilt Quilt
Kilt Quilt
题目描述
给定一幅由 行、 列像素构成的目标图像,每个像素的颜色用一个小写英文字母表示。
你需要通过若干次整行或整列涂色,在一块空白画布上得到完全相同的图像。每次操作只能选择以下两种方式之一:
- 选择一整行,将该行的所有 个像素涂成同一种颜色;
- 选择一整列,将该列的所有 个像素涂成同一种颜色。
后执行的操作会覆盖之前对同一像素的涂色。要求最终画布的每个像素都至少被涂过一次,并且最终颜色与目标图像一致。
判断能否完成。如果可以,输出一种操作次数最少的涂色方案。
图示(重绘示意图)

图 K.1:样例 2 的目标图像及一种最优的整行、整列涂色操作序列。 本图为重绘示意图。
输入格式
第一行输入两个整数 。
接下来 行,每行一个长度为 的小写英文字母串,表示目标图像的颜色。
输出格式
若无法完成,输出:
impossible
否则,第一行输出一个整数 ,表示实现目标图像所需的最少操作次数。
接下来输出 行操作,每行的格式为下列两种之一:
x=c ch:将第 列()全部涂成颜色ch;y=r ch:将第 行()全部涂成颜色ch。
这里 ch 是一个小写英文字母,操作必须按照输出顺序执行。若最优方案不唯一,可输出任意一种。
样例 #1
输入
4 6
aaaaba
aaaaba
aaaaba
aaaaba
输出(答案不唯一)
5
y=1 a
y=2 a
y=3 a
y=4 a
x=5 b
样例 #2
输入
4 4
laaq
daaq
laaq
bbbq
输出(答案不唯一)
6
x=1 l
y=2 d
x=2 a
x=3 a
y=4 b
x=4 q
数据范围与保证
- ;
- 图像仅包含
a到z的小写英文字母。