#LQB0057. 迷宫走珠

迷宫走珠

提示信息: 迷宫走珠是一种物理益智玩具,使用透明外壳包裹各种迷宫通道,玩家通过调整迷宫方向引导钢珠穿越复杂路径完成通关。

编程实现:
本题的迷宫走珠可以看作一个 n 行 n 列的网格(左上角为第一行第一列),每一行都有一个单元格为缺口,缺口可以让钢珠下落到下一行对应的单元格。迷宫走珠初始竖直摆放,钢珠初始在第一行第x列的单元格,游游要让钢珠从第一行开始,通过倾斜或竖直摆放迷宫使得钢珠朝着调整的方向移动,钢珠移动到缺口处时会掉落到下一行并继续朝着调整的方向移动,重复这个操作直到钢珠最终到达迷宫第n 行的缺口。 注:当上一行的缺口和当前这一行的缺口在同一列时,需在当前行将迷宫竖直摆放。
给定 n 行 n 列的网格,以及每一行的缺口位置,钢珠初始在第一行第 x 列的单元格。请帮助游游操作迷宫走珠,钢珠在每一行时应往哪个方向调整,向左倾斜时输出 L,向右倾斜时输出R,竖直摆放时输出U。
例如,n = 5,迷宫走珠为 5 行 5 列的网格;x = 2,钢珠初始在第一行第2 列的单元格(虚线仅为区分单元格,实际过程中并不存在):

游游应该这样操作迷宫走珠,钢珠在第一行时向右倾斜,第二行时向左倾斜,第三行时向右倾斜,第四行时竖直摆放,第五行时向右倾斜。

所以输出 RLRUR。

输入格式

第一行输入一个整数 nn,表示迷宫走珠的行列数。
第二行输入一个整数 xx,表示钢珠初始在第 11 行的单元格位置。
接下来输入 nn 行,每行输入 nn 个整数(整数为 1100),11 表示该单元格是缺口,00 表示该单元格不是缺口,每行整数之间以一个空格隔开。

数据保证每行仅有一个单元格是缺口,且钢珠初始位置与第 11 行的缺口位置不同。

输出格式

输出一个长度为 nn 的字符串,字符串从左到右依次表示游游在每一行时应采取的操作,用 L 表示向左倾斜、U 表示竖直摆放、R 表示向右倾斜。

样例输入输出

样例输入1

5
2
0 0 0 1 0
1 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 1 0

样例输出1

RLRUR

数据范围与测试点说明

  • 3n10003\le n\le 1000
  • 1xn1\le x\le n
  • 输入仅包含 0011
  • 每行恰好一个缺口(即恰好一个 11)。
  • 钢珠初始位置与第 11 行缺口位置不同。

时间限制与内存限制

  • 时间限制:11
  • 内存限制:10241024 KiB