Moving Floors and a Switch

2 secs 1024 MB
setsuna's icon setsuna

問題文

HHWW 列に並べられた動く床の上に何匹かのスライムがいます。 上から ii 行目、左から jj 列目の動く床を (i,j)(i,j) と表します。 動く床はそれぞれ状態A, Bの2つの状態をもちます。また、動く床はいずれの状態においても上下左右のいずれかの方向に動いています。 (i,j)(i,j) が状態A, Bのときに動く方向はそれぞれ文字 Ai,j,Bi,jA_{i,j}, B_{i,j} によって表されます。 Ai,jA_{i,j} の意味は次のとおりです。

  • Ai,jA_{i,j}U のとき、(i,j)(i,j) は上向き、すなわち (i1,j)(i-1, j) の方向に動いている。
  • Ai,jA_{i,j}D のとき、(i,j)(i,j) は下向き、すなわち (i+1,j)(i+1, j) の方向に動いている。
  • Ai,jA_{i,j}L のとき、(i,j)(i,j) は左向き、すなわち (i,j1)(i, j-1) の方向に動いている。
  • Ai,jA_{i,j}R のとき、(i,j)(i,j) は右向き、すなわち (i,j+1)(i, j+1) の方向に動いている。

なお、Bi,jB_{i,j} も同様です。また、どの床も床のない方向には動いていないことが保証されます。

ここで、スイッチが搭載された動く床がちょうど 11 つだけ存在します。スイッチが搭載された動く床は (is,js)(i_s, j_s) で与えられます。 スライムが (is,js)(i_s, j_s) に到達すると、その瞬間にスイッチが作動し、以下の変化が生じます。

  • スイッチの作動が奇数回目 (1回目,3回目,)(1回目, 3回目, \cdots) ならば、(i,j)(i,j) が動く方向は Ai,jA_{i,j} から Bi,jB_{i,j} に切り替わる。
  • スイッチの作動が偶数回目 (2回目,4回目,)(2回目, 4回目, \cdots) ならば、(i,j)(i,j) が動く方向は Bi,jB_{i,j} から Ai,jA_{i,j} に切り替わる。

現在、(i,j)(i,j) にスライムがいるかどうかが Si,jS_{i,j} によって与えられます。 Si,jS_{i,j}(i,j)(i,j) にスライムがいるなら #、いないなら . です。 ただし、スイッチが搭載された動く床 (is,js)(i_s, j_s) にはスライムがいないことが保証されます。

11 秒経過する毎に各スライムはそのときにいる床が動く方向に移動します。 なお、22 匹以上のスライムが同じ床に移動した場合、それらのスライムは合体して 11 匹のスライムになります。

現在から tt 秒後のスライムの配置を出力してください。

制約

  • H,W,t,is,jsH, W, t, i_s, j_s は正整数
  • 1H×W<201 \leq H \times W < 20
  • 1t10181 \leq t \leq 10^{18}
  • 1isH1 \leq i_s \leq H
  • 1jsW1 \leq j_s \leq W
  • Ai,j,Bi,jA_{i,j}, B_{i,j}U, D, L, R のいずれかである
  • A1,jA_{1,j} \neq U, B1,jB_{1,j} \neq U
  • AH,jA_{H,j} \neq D, BH,jB_{H,j} \neq D
  • Ai,1A_{i,1} \neq L, Bi,1B_{i,1} \neq L
  • Ai,WA_{i,W} \neq R, Bi,WB_{i,W} \neq R
  • Si,jS_{i,j}#, . のいずれかである

入力

入力は以下の形式で標準入力から与えられます。

HH WW tt isi_s jsj_s
A1,1A1,WA_{1, 1} \cdots A_{1, W}
\vdots
AH,1AH,WA_{H, 1} \cdots A_{H, W}
B1,1B1,WB_{1, 1} \cdots B_{1, W}
\vdots
BH,1BH,WB_{H, 1} \cdots B_{H, W}
S1,1S1,WS_{1, 1} \cdots S_{1, W}
\vdots
SH,1SH,WS_{H, 1} \cdots S_{H, W}

出力

tt 秒後、(i,j)(i,j) にスライムがいるかどうかを表す Ti,jT_{i,j} を以下の形式で出力してください。 Ti,jT_{i,j}tt 秒後、(i,j)(i,j) にスライムがいるなら #、いないなら . です。

T1,1T1,WT_{1, 1} \cdots T_{1, W}
\vdots
TH,1TH,WT_{H, 1} \cdots T_{H, W}

入出力例

入力例1
3 3 10 3 3
RRD
URD
ULL
DLL
DRU
RRU
#..
...
...
出力例1
...
...
#..

初め (1,1)(1, 1) にいるスライムは 44 秒だけかけて (1,1)(1,2)(1,3)(2,3)(3,3)(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) と移動します。(3,3)(3, 3) にはスイッチがあり、スイッチが作動することで動く床の状態が変化します。 その後、スライムは 66 秒だけかけて (3,3)(2,3)(1,3)(1,2)(1,1)(2,1)(3,1)(3, 3) \rightarrow (2, 3) \rightarrow (1, 3) \rightarrow (1, 2) \rightarrow (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) と移動します。よって、1010 秒後には (3,1)(3, 1) にいます。

入力例2
2 3 10 2 2
RDL
RUL
RRD
ULL
#.#
#..
出力例2
..#
#..

初め (1,1),(1,3)(1, 1), (1, 3) にいる 22 匹のスライムは 11 秒後に (1,2)(1, 2) で合体します。

入力例3
4 2 1000000000000000000 1 1
RD
UL
RD
UL
RL
UD
UU
UL
..
.#
#.
##
出力例3
#.
..
.#
..

入力値 tt が32bit整数型に収まらないこともあります。

提出


Go (1.21)