QOJ.ac

QOJ

حد الوقت: 1 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓

#17529. 为饥饿的Muto制作披萨

الإحصائيات

凯内西斯在探索啾啾岛以讨伐黑魔法师的过程中,遇到了饥饿的姆托。一直负责为姆托准备每日餐食的西米亚,为了制作能满足姆托胃口的大型披萨,向凯内西斯寻求帮助。由于体型巨大的姆托挡住了通往黑魔法师的道路,凯内西斯不得不答应西米亚的请求。

姆托想要的巨大披萨是一个 $N \times N$ 的网格,披萨左上角的格子为第 $1$ 行第 $1$ 列,右下角的格子为第 $N$ 行第 $N$ 列。西米亚给出的食谱上画有披萨上肉丸的布局,凯内西斯需要按照食谱放置肉丸。起初,披萨的第 $R$ 行第 $C$ 列已经放置了一颗西米亚预先放好的肉丸。肉丸的形状与网格完全吻合,且一个格子内不能放置超过一颗肉丸。

$N=5, R=3, C=2$ 时披萨的状态以及在披萨外使用念力的位置

由于踩到披萨会导致其无法食用,凯内西斯必须在披萨外使用念力来完成披萨的制作。使用一次念力的过程如下:

  1. 确定使用念力的位置。可选位置为披萨的上、下、左、右四个方向。念力从凯内西斯所在位置开始,若在上方则向行增加的方向作用,若在下方则向行减小的方向作用,若在左方则向列增加的方向作用,若在右方则向列减小的方向作用。
  2. 确定使用念力的行号或列号。念力必须与行或列平行使用,且不能同时作用于两行或两列以上。
  3. 使用念力。念力分为两种:
    • 推入 (push):将肉丸推入,并将其放置在撞到的第一颗肉丸的前一个格子中。如果在推入前,念力作用方向的第一个格子已有肉丸,或者因为该方向没有肉丸导致推入的肉丸无法留在披萨内,则该肉丸消失。
    • 拉出 (pull):将念力接触到的第一颗肉丸从披萨中取出。如果念力作用方向上没有肉丸,则什么都不会发生。

使用推入 (push) 和拉出 (pull) 念力的示意图

如果按照西米亚的食谱完成了披萨,姆托就会吃得心满意足,并让出通往下一个区域的道路。但由于不知道黑魔法师何时会毁灭世界,凯内西斯不能在制作披萨上浪费时间。

请输出一种在 $2N^2$ 次以内使用念力完成披萨的方法。

第一行给定披萨的大小 $N$。($3 \leq N \leq 50$)

第二行给定西米亚最初放置的肉丸所在的行号 $R$ 和列号 $C$,中间用空格隔开。($1 \leq R, C \leq N$)

接下来 $N$ 行给出西米亚食谱上的肉丸布局。每行给出一个长度为 $N$ 的字符串。食谱第 $i$ 行的第 $j$ 个字符表示第 $i$ 行第 $j$ 列是否有肉丸,. 表示空格,# 表示放置了肉丸的格子。

如果能在 $2N^2$ 次以内使用念力完成披萨,第一行输出凯内西斯使用念力的次数 $M$。注意,$M$ 不需要是最小值。($0 \leq M \leq 2N^2$)

若 $M \geq 1$,则从第二行开始,每行输出一次凯内西斯执行的动作。每行包含使用念力的位置(上方:U,下方:D,左方:L,右方:R)、行号或列号 $X$ ($1 \leq X \leq N$) 以及念力的种类(推入为 push,拉出为 pull),中间用空格隔开。

如果无法在 $2N^2$ 次以内完成披萨,第一行仅输出 -1

样例

输入格式 1

3
2 2
.#.
##.
...

输出格式 1

2
U 2 push
L 2 push

输入格式 2

3
1 2
...
#.#
.#.

输出格式 2

6
D 2 push
D 2 push
L 2 push
R 2 push
U 2 pull
U 2 pull

输入格式 3

4
1 1
....
....
....
....

输出格式 3

1
L 1 pull

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.