#P18571. [ukiepc2026]Lawn Stripes

[ukiepc2026]Lawn Stripes

Lawn Stripes

题目描述

一块正方形草坪被划分为 n×nn\times n 个大小为 1×11\times1 米的方格。你有一台压草滚筒,可以沿上、下、左、右四个方向移动,在经过的格子中留下该方向的草坪纹路。

滚筒必须始终位于草坪内。一个格子的最终纹路方向取决于滚筒最后一次经过该格子时的移动方向;移动的起点格子和终点格子也受到该次移动方向的影响。

现给出滚筒的初始位置,以及每个格子最终期望的纹路方向。请判断能否通过一系列合法移动得到目标图案。

如果能够做到,输出一种满足要求的移动方案,并保证移动次数严格小于 10n210n^2。如果做不到,输出 impossible。

图示(重绘示意图)

图 L.1:样例 1 的目标草坪方向、颜色图例和对应的压草移动路径。

图 L.1:样例 1 的目标草坪方向、颜色图例和对应的压草移动路径。 本图为重绘示意图。

输入格式

第一行输入整数 nn,表示草坪的行数与列数。

第二行输入两个整数 r,cr,c,表示滚筒初始所在的行、列(从 11 开始编号)。

接下来的 nn 行,每行一个长度为 nn 的字符串,只包含以下四种字符:

  • l:最终纹路向左;
  • r:最终纹路向右;
  • u:最终纹路向上;
  • d:最终纹路向下。

输出格式

如果无法完成,输出一行:

impossible

否则,第一行输出整数 qq,表示移动操作数,要求 q<10n2q<10n^2。

接下来输出 qq 行,每行两个量:

d dir

其中 dd 表示沿指定方向行走的距离(单位:米),dir 为 l、r、u、d 中的一个。

执行全部操作时,滚筒不得越出草坪;所有方格都必须被滚筒经过,最终纹路必须与输入完全一致。

样例 #1

输入

4
1 4
rrrd
llll
rrru
ulll

输出(答案不唯一)

8
3 l
3 r
3 d
3 l
1 u
3 r
1 u
3 l

样例 #2

输入

2
1 1
rd
ul

输出

impossible

数据范围与保证

  • 1≤n≤1001\le n\le100;
  • 1≤r,c≤n1\le r,c\le n;
  • 目标图案由 l、r、u、d 四个方向字符组成。