QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓

#17529. 為飢餓的穆托製作披薩

统计

凱內西斯在探索啾啾島以討伐黑魔法師的過程中,遇見了飢餓的慕托。為了慕托每天準備餐點的西米亞,請求凱內西斯幫忙製作一個大披薩,以安撫鬧脾氣的慕托。由於體型巨大的慕托擋住了前往黑魔法師所在地的路,凱內西斯只好答應西米亞的請求。

慕托想要的巨大披薩是一個 $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.