AT_kupc2019_i encode/decode 2019
题目描述
**注意：这是一道包含交互元素的题目。**
您将获得一个在 $0$ 到 $10^{18}$ 之间的整数 $X$。
请仔细阅读下列说明，并编写两个程序：一个用于编码整数 $X$ 的 `encode` 程序，另一个用于解码以找回 $X$ 的 `decode` 程序。
如果 `decode` 程序能仅通过 `encode` 程序编码后的信息准确恢复 $X$，则结果视为正确。
### encode 程序
在 `encode` 程序中，您需要将输入的整数 $X$ 编码为一个 $150 \times 150$ 的网格 $H$。
首先，您会得到一个整数 $X$ 和一个 $150 \times 150$ 的初始网格 $G$。网格 $G$ 中的元素可能是空格 `.` 或墙壁 `#`，这些墙壁是根据特定规则生成的。
您需要通过以下三种操作之一对网格 $G$ 中的每一个空格 `.` 进行处理，进而生成并输出网格 $H$：
- 将其替换为墙壁 `#`；
- 将其替换为 S 格 `S`；
- 保持为空格 `.`。
重要的是，在网格 $H$ 中，S 格必须且只能有一个。
### decode 程序
在 `decode` 程序中，您的任务是从网格 $H$ 的信息中解码出整数 $X$。
网格 $H$ 的信息并不会直接提供给您，而是让您控制一个在网格 $H$ 上的机器人进行一系列操作。
我们将网格中的第 $i$ 行第 $j$ 列的格子称为格子 $(i, j)$。初始时，机器人位于S格。通过多次以下的**“操作”**，您可以解码出整数：
- 指示机器人向上下左右四个方向中的一个移动。
- 机器人会尝试从当前位置向指定方向的相邻格子移动。
- 如果机器人当前在格子 $(i, j)$，那么：
- 上：移动至 $(i-1, j)$；
- 下：移动至 $(i+1, j)$；
- 左：移动至 $(i, j-1)$；
- 右：移动至 $(i, j+1)$。
- 机器人移动的条件是目的地格子不是墙壁 `#`，且该目的地不在网格之外。否则，它会停留在原地。
- 随后，您会收到关于机器人是否在 S 格上的反馈。
- 您并不知道机器人是否成功移动。
在进行一系列**“操作”**后，您需要输出您解码出的整数 $X$。
### 初始网格生成
初始网格 $G$ 共包括 $3800$ 个随机分布的墙壁 `#`。
保证每一堵墙周围8个格子中都不会有其他的墙。
具体生成步骤如下：
- 最初整个网格均为空格 `.`。
- 不断随机选择周围格子均为`.`的空格，替换为墙壁 `#`，直到放置了 $3800$ 个墙壁。
- 这一过程中如果无法再放置墙壁，则放弃该网格，重新生成整个网格。
- 重复这一过程，直到成功放置 $3800$ 个墙壁。
这种方法生成的初始网格样本，我们提供了 [50个样本](https://drive.google.com/drive/folders/1-lzvjvWZs9zsJjMVK0jLNRrIqCnwlfFB?usp=sharing)。
注意：提供的样本并不一定用于实际测试。
### 约束
- $0 \leq X \leq 10^{18}$，$X$ 为随机选择。
- 网格尺寸为 $150 \times 150$。
- 初始网格 $G$ 包含 $3800$ 墙壁 `#`。
- 墙壁周围的 8 个格子中没有其他墙。
- 每次提交都会生成新的整数 $X$ 和初始网格 $G$。
### 部分得分
本题设置了部分分数。
对于每次提交所生成的 $25$ 个测试用例中任何一例：
- 若在 $65000$ 次或更少的**“操作”**内正确解码，您将得到 $10$ 分；同时
- 若在 $6500$ 次或更少的**“操作”**内正确解码，您将额外得到 $390$ 分。
### 提交
将 `encode` 程序和 `decode` 程序组合为一个文件进行提交。
根据下面的“评测说明”，提交的程序会分别以编码和解码模式被调用各一次。
程序启动时会输入一个字符串以指示当前是编码还是解码。
### 输入（encode 程序）
输入是通过标准输入以以下形式给出的。
第一行为字符串 `encode`。
第二行为整数 $X$，第三行及以后各行为初始网格 $G$。
$G$ 中的格子 $(i, j)$ 由字符 $G_{i,j}$ 表示。
- 若格子 $(i, j)$ 为空格，则 $G_{i,j}$ 是 `.`；
- 若格子 $(i, j)$ 为墙壁，则 $G_{i,j}$ 是 `#`。
无字符间空格：
```
encode
X
G_{1,1}G_{1,2}...G_{1,150}
:
G_{150,1}G_{150,2}...G_{150,150}
```
### 输出（encode 程序）
请按照以下格式将网格 $H$ 输出到标准输出。
网格 $H$ 中的格子 $(i, j)$ 用字符 $H_{i,j}$ 表示。
- 若格子 $(i, j)$ 为空格，则 $H_{i,j}$ 是 `.`；
- 若格子 $(i, j)$ 为墙壁，则 $H_{i,j}$ 是 `#`；
- 若格子 $(i, j)$ 为 S 格，则 $H_{i,j}$ 是 `S`。
无字符间空格：
```
H_{1,1}H_{1,2}...H_{1,150}
:
H_{150,1}H_{150,2}...H_{150,150}
```
### 输入输出（decode 程序）
程序将以以下形式从标准输入接收字符串 `decode`：
```
decode
```
随后进行一系列**“操作”**。在每次**“操作”**中，请按照以下格式输出您希望机器人的移动方向：
方向用 $C$ 表示，可能取 `U`, `D`, `L`, `R` 中的一个，分别表示上下左右四个方向。
```
? C
```
对该**“操作”**的响应将按照以下格式从标准输入给出。
反馈中用 $J$ 表示机器人是否在S 格上：
- 如果在，则 $J$ 为 `S`；
- 如果不在，则 $J$ 为 `.`。
```
J
```
最后，请按照以下格式输出您解码出的整数 $X$：
```
! X
```
### 评测说明
评测将按照下面的步骤进行：
- 生成随机整数 $X$ 和初始网格 $G$。
- 编码环境中启动提交的程序。
- 将输入传给编码环境的程序，不发送EOF。
- 程序输出正确的编码后，可正常终止程序。
- 输入无效网格将被判为错误。
- 解码环境中启动提交的程序。
- 与解码程序交互，直至其结束。
- 如果在时间限制内获得正确输出，则判定为正确，否则判定错误。
### 注意事项
- 每次输出后请刷新标准输出，否则可能会导致超时。
- 输出网格 $H$ 和整数 $X$ 后，请立即终止程序，否则行为未定义。
- 输出格式不符合要求时，评测结果未定义。
- **程序不得执行任何未明示批准的通信操作。**
### 输入样例（encode 程序）
此例中，网格 $G$ 为 $20 \times 20$，实际为 $150 \times 150$。
墙壁数量为 $70$，实际应为 $3800$。
```
encode
239
#..............#..#.
......#....#.#......
..#............#....
.....#..#..#.#...#..
.#.#...............#
.......#..#..#......
..#..#.........#.#.#
..........#..#......
..#..#..........#.#.
.......#.#..#.......
...#..........#...#.
.#...#...#.#........
.......#.....#.#..#.
#.#......#.#........
....#.#.......#..#..
.........#.........#
#..#.#.#...#.#.#.#..
...................#
..#.....#.#.#.......
.....#.........#.#..
```
### 输出样例（encode 程序）
此例中，网格 $H$ 为 $20 \times 20$，实际为 $150 \times 150$。
```
####################
#S...###############
..##...#############
######.#############
#####..#############
#.....##############
..######....########
.#####...##..#######
.##########..#######
......####..########
########...#########
##########.#.....###
####..##...#.###..##
#####....###.####..#
############..####.#
#############......#
##################.#
############..###..#
#############.....##
####################
```
### 输入输出样例（decode 程序）
这是在上面的编码示例后的解码过程的示例。
输入 输出 备注
```
decode
```
解码开始。机器人在 S 格坐标 $(2, 2)$。
```
? R
```
机器人向右移动到空格 $(2, 3)$。
```
.
```
机器人位于空格中。
```
? U
```
机器人尝试往上到墙 $(1, 3)$，但失败，仍在 $(2, 3)$。
```
.
```
机器人仍然在空格中。
```
? L
```
机器人移动回 S 格 $(2, 2)$。
```
S
```
机器人此时在 S 格。
```
! 239
```
输出 $X$，过程结束. **“操作”**次数为 $3$ 次。
**本翻译由 AI 自动生成**
输入格式
无
输出格式
无
说明/提示
### encode プログラム
encode プログラムでは、与えられた整数 $ X $ を $ 150 $ 行 $ 150 $ 列のグリッド $ H $ に符号化する。
まず、整数 $ X $ および $ 150 $ 行 $ 150 $ 列の初期グリッド $ G $ の情報が入力される。
$ G $ の各マスは空マス `.` か壁マス `#` のいずれかであり、後述する**「初期グリッド生成」**によって生成される。
あなたは $ G $ の空マス `.` それぞれについて以下のいずれかを行うことでグリッド $ H $ を作り、出力しなければならない。
- 壁マス `#` に置き換える。
- Sマス `S` に置き換える。
- 空マス `.` のままにする。
ただしグリッド $ H $ において、Sマスはグリッド上に必ず $ 1 $ マスだけ存在するようにしなければならない。
### decode プログラム
decode プログラムでは、グリッド $ H $ の情報から整数 $ X $ を復号する。
ただし、 $ H $ の情報は直接入力されない。その代わりに、グリッド $ H $ 上にいるロボットを操作することができる。
グリッドの $ i $ 行 $ j $ 列目のマスを、マス $ (i,\ j) $ と呼ぶことにする。
はじめ、ロボットは $ H $ の Sマスにいる。あなたは以下の**「操作」**を何回か行うことができる。
- 上下左右の $ 4 $ 方向のうちの $ 1 $ つをロボットに伝える。
- ロボットは、現在いるマスからその向きにある隣り合ったマスに移動しようとする。
- つまり、ロボットがマス $ (i,\ j) $ にいるとすると、
- ロボットに伝えた方向が上であるとき、ロボットはマス $ (i-1,\ j) $ に、
- ロボットに伝えた方向が下であるとき、ロボットはマス $ (i+1,\ j) $ に、
- ロボットに伝えた方向が左であるとき、ロボットはマス $ (i,\ j-1) $ に、
- ロボットに伝えた方向が右であるとき、ロボットはマス $ (i,\ j+1) $ に移動しようとする。
- そのマスが壁マス `#` でなく、グリッドの外でもなければ移動し、壁マス `#` かグリッドの外であれば移動しない。
- その後、ロボットが Sマスにいるかどうかがあなたに伝えられる。
- ロボットの移動が成功したかどうかはあなたには伝えられない。
何回かの**「操作」**の後、あなたは復号した整数 $ X $ を出力しなければならない。
### 初期グリッド生成
初期グリッド $ G $ には $ 3800 $ 個の壁マス `#` がランダムに配置されている。
壁マスの周囲 $ 8 $ マスには、他の壁マスが存在しないことが保証されている。
マス $ (i,\ j) $ の周囲 $ 8 $ マスとは、マス $ (i-1,\ j-1) $, $ (i-1,\ j) $, $ (i-1,\ j+1) $, $ (i,\ j-1) $, $ (i,\ j+1) $, $ (i+1,\ j-1) $, $ (i+1,\ j) $, $ (i+1,\ j+1) $ のことである。
具体的には、初期グリッドは以下のように生成される。
- はじめ、グリッドのすべてのマスは空マス `.` である。
- $ 3800 $ 個の壁マスが置かれるまで以下を繰り返す。
- 周囲 $ 8 $ マスに壁マスがないような空マスを候補として列挙し、その中からランダムに $ 1 $ つのマスを選び、それを壁マスに置き換える。
- グリッドの縁にある空マスについても同様に、その周りに壁マスがなければ候補に含まれる。
- もしそのようなマスがなく、$ 3800 $ 個の壁マスを置くことができないことがわかったら、そのグリッドを捨てて、新しくグリッドを生成しなおす。
- $ 3800 $ 個の壁マスが置かれたら、このグリッドを初期グリッドとして採用する。
この方法によって生成された初期グリッドのサンプル $ 50 $ 個が、[共有フォルダ](https://drive.google.com/drive/folders/1-lzvjvWZs9zsJjMVK0jLNRrIqCnwlfFB?usp=sharing) にて配布されている。
なお、これらの配布されているグリッドが実際のテストケースに含まれているとは限らない。
### 制約
- $ 0\ \leq\ X\ \leq\ 10^{18} $
- $ X $ はこの範囲からランダムに選ばれる整数である。
- グリッドの縦幅および横幅は $ 150 $ マスである。
- 初期グリッド $ G $ の壁マス `#` の個数は $ 3800 $ である。
- 初期グリッド $ G $ では、壁マスの周囲 $ 8 $ マスには他の壁マスは配置されない。
- 整数 $ X $ および初期グリッド $ G $ は、解答コードの提出ごとに新しく生成される。
### 部分点
この問題には部分点が設定されている。
解答コードの提出ごとに新しく生成される $ 25 $ 個のどのテストケースに対しても、
- $ 65000 $ 回以下の**「操作」**によって正答した場合は、 $ 10 $ 点
- $ 6500 $ 回以下の**「操作」**によって正答した場合は、上に加えて $ 390 $ 点
が与えられる。
### 提出
encode プログラムと decode プログラムを $ 1 $ つにまとめ、提出せよ。
後述する「ジャッジ」をみればわかるように、提出されたプログラムは encode 用と decode 用に $ 1 $ 回ずつ起動される。
プログラム起動時には、符号化と復号のどちらを行えばよいかを判別するための文字列が入力される。
### 入力 （encode プログラム）
入力は以下の形式で標準入力から与えられる。
$ 1 $ 行目には文字列 `encode` が与えられる。
$ 2 $ 行目には $ X $ が入力され、 $ 3 $ 行目以降には $ G $ が入力される。
$ G $ のマス $ (i,\ j) $ は文字 $ G_{i,j} $ で表わされる。
- マス $ (i,\ j) $ が空マスのとき $ G_{i,j} $ は文字 `.` であり、
- マス $ (i,\ j) $ が壁マスのとき $ G_{i,j} $ は文字 `#` である。
文字の間に空白は含まれない。
> encode $ X $ $ G_{1,1} $$ G_{1,2} $$ ... $$ G_{1,150} $ $ : $ $ G_{150,1} $$ G_{150,2} $$ ... $$ G_{150,150} $
### 出力 （encode プログラム）
標準出力へ以下の形式で $ H $ を出力せよ。
$ H $ のマス $ (i,\ j) $ を文字 $ H_{i,j} $ で表せ。
- マス $ (i,\ j) $ が空マスのとき $ H_{i,j} $ は文字 `.`、
- マス $ (i,\ j) $ が壁マスのとき $ H_{i,j} $ は文字 `#`、
- マス $ (i,\ j) $ がSマスのとき $ H_{i,j} $ は文字 `S` とせよ。
文字の間に空白を含めてはいけない。
> $ H_{1,1} $$ H_{1,2} $$ ... $$ H_{1,150} $ $ : $ $ H_{150,1} $$ H_{150,2} $$ ... $$ H_{150,150} $
### 入出力 （decode プログラム）
最初に、文字列 `decode` が次の形式で標準入力から与えられる。
```
decode
```
その後、何回か**「操作」**を行う。**「操作」**では次の形式で標準出力へ出力せよ。
ロボットに移動させたい方向を文字 $ C $ で表せ。$ C $ は文字 `U`,`D`,`L`,`R` のいずれかであり、それぞれ上下左右の $ 4 $ 方向を表す。
> ? $ C $
この**「操作」**に対する応答は、次の形式で標準入力から与えられる。
ロボットがSマスにいるかどうかが文字 $ J $ で表される。
- ロボットがSマスにいるとき $ J $ は `S` であり、
- ロボットがSマスにいないとき $ J $ は `.` である。
> $ J $
最後に $ X $ を以下の形式で出力せよ。
> ! $ X $
### ジャッジ
ジャッジは以下の手順で行われる。
- 整数 $ X $ および初期グリッド $ G $ を生成する。
- 提出されたプログラムのプロセスを encode 用として立ち上げる。
- encode 用のプロセスに入力を与える。ただし、EOF は与えない。
- encode 用のプロセスから適切な出力があり、かつ encode 用のプロセスが終了するまで待機する。
- 不適切なグリッドが出力された場合は誤答とする。
- 提出されたプログラムのプロセスを decode 用として立ち上げる。
- decode 用のプロセスと対話を行う。この対話は decode 用のプロセスが終了するまで続く。
- 実行時間制限内に decode 用のプロセスから正しい出力がなされた場合のみ正答とし、それ以外は誤答とする。
### 注意
- 出力の度に標準出力を flush せよ。そうしない場合、TLE となる可能性がある。
- グリッド $ H $ および整数 $ X $ を出力した後は、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は未定義である。
- 出力形式が正しくない場合のジャッジの挙動は未定義である。
- **プロセスは、上記によって規定された以外のいかなる通信も行ってはならない。**
### 入力例（encode プログラム）
この例では $ G $ は $ 20 $ 行 $ 20 $ 列のグリッドとして入力されているが、実際には $ 150 $ 行 $ 150 $ 列である。
また、 この例では $ G $ の壁マスの個数は $ 70 $ 個だが、実際には $ 3800 $ 個である。
```
encode
239
#..............#..#.
......#....#.#......
..#............#....
.....#..#..#.#...#..
.#.#...............#
.......#..#..#......
..#..#.........#.#.#
..........#..#......
..#..#..........#.#.
.......#.#..#.......
...#..........#...#.
.#...#...#.#........
.......#.....#.#..#.
#.#......#.#........
....#.#.......#..#..
.........#.........#
#..#.#.#...#.#.#.#..
...................#
..#.....#.#.#.......
.....#.........#.#..
```
### 出力例 （encode プログラム）
この例では $ H $ は $ 20 $ 行 $ 20 $ 列のグリッドとして出力されているが、実際には $ 150 $ 行 $ 150 $ 列である。
```
####################
#S...###############
..##...#############
######.#############
#####..#############
#.....##############
..######....########
.#####...##..#######
.##########..#######
......####..########
########...#########
##########.#.....###
####..##...#.###..##
#####....###.####..#
############..####.#
#############......#
##################.#
############..###..#
#############.....##
####################
```
### 入出力例 （decode プログラム）
符号化が上記の入出力例のように行われた後の復号の例を示す。
入力 出力 備考 ```
decode
```
decodeが開始される。ロボットはSマス $ (2,\ 2) $ にいる。 ```
? R
```
ロボットは空マス $ (2,\ 3) $ に移動する。 ```
.
```
ロボットは空マスにいる。 ```
? U
```
ロボットはマス $ (1,\ 3) $ に移動しようとするが、このマスは壁マスであるため、 もとのマス $ (2,\ 3) $ にとどまる。 ```
.
```
ロボットは空マスにいる。 ```
? L
```
ロボットはSマス $ (2,\ 2) $ に移動する。 ```
S
```
ロボットはSマスにいる。 ```
! 239
```
$ X $ を出力し、プログラムを終了する。**「操作」**の回数は $ 3 $ 回である。