#P18570. [ukiepc2026]Kilt Quilt

[ukiepc2026]Kilt Quilt

Kilt Quilt

题目描述

给定一幅由 nn 行、mm 列像素构成的目标图像,每个像素的颜色用一个小写英文字母表示。

你需要通过若干次整行或整列涂色,在一块空白画布上得到完全相同的图像。每次操作只能选择以下两种方式之一:

  • 选择一整行,将该行的所有 mm 个像素涂成同一种颜色;
  • 选择一整列,将该列的所有 nn 个像素涂成同一种颜色。

后执行的操作会覆盖之前对同一像素的涂色。要求最终画布的每个像素都至少被涂过一次,并且最终颜色与目标图像一致。

判断能否完成。如果可以,输出一种操作次数最少的涂色方案。

图示(重绘示意图)

图 K.1:样例 2 的目标图像及一种最优的整行、整列涂色操作序列。

图 K.1:样例 2 的目标图像及一种最优的整行、整列涂色操作序列。 本图为重绘示意图。

输入格式

第一行输入两个整数 n,mn,m。

接下来 nn 行,每行一个长度为 mm 的小写英文字母串,表示目标图像的颜色。

输出格式

若无法完成,输出:

impossible

否则,第一行输出一个整数 qq,表示实现目标图像所需的最少操作次数。

接下来输出 qq 行操作,每行的格式为下列两种之一:

  • x=c ch:将第 cc 列(1≤c≤m1\le c\le m)全部涂成颜色 ch;
  • y=r ch:将第 rr 行(1≤r≤n1\le r\le n)全部涂成颜色 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

数据范围与保证

  • 1≤n,m≤2001\le n,m\le200;
  • 图像仅包含 a 到 z 的小写英文字母。