問題一覧 > 通常問題

No.1427 Simplified Tetris

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 24
作問者 : 👑 koboshikoboshi / テスター : 👑 maspymaspy
3 ProblemId : 5477 / 出題時の順位表
問題文最終更新日: 2021-03-16 15:57:16

問題文

$H$ 行 $W$ 列のマス目があります。初めはどのマスにもブロックは置かれていません。このマス目に以下の操作を $0$ 回以上行います。

  • 操作 (配置): まだブロックが置かれていない隣り合う (一辺を共有する) $2$ マスを選び、それぞれにブロックを置く。

その後、次の操作を行います。

  • 操作 (削除): すべてのマスにブロックが置かれているような各行に対し、その行に置かれているブロックをすべて削除する。

さらにその後、次の操作を行います。

  • 操作 (落下): $i$ 行目にブロックが存在し、$i+1$ 行目にブロックが存在しないとき、$i$ 行目と $i+1$ 行目を入れ替える。これを操作が行えなくなるまで繰り返す。

これらの操作をすべて行った後のマス目の状態 $s$ が与えられます。$s_{ij}$ が.のとき $i$ 行目 $j$ 列目のマスにはブロックが置かれていないことを表し、$s_{ij}$ が#のとき $i$ 行目 $j$ 列目のマスにはブロックが置かれていることを表します。この状態を達成するような操作 (配置) の方法を $1$ つ求めてください。

入力

$H$ $W$
$s_{11}s_{12}\ldots s_{1W}$
$s_{21}s_{22}\ldots s_{2W}$
$\vdots$
$s_{H1}s_{H2}\ldots s_{HW}$
  • $1\le H,W\le 10$
  • $H,W$ は整数
  • $s_{ij}$ は.または#

出力

条件を満たす操作 (配置) の方法が存在しない場合はNoと出力してください。

条件を満たす操作 (配置) の方法が存在する場合は以下のように出力してください。

Yes
$t_{11}t_{12}\ldots t_{1W}$
$t_{21}t_{22}\ldots t_{2W}$
$\vdots$
$t_{H1}t_{H2}\ldots t_{HW}$

$i$ 行目 $j$ 列目のマスにブロックを置かない場合は $t_{ij}$ を.とし、ブロックを置く場合は $t_{ij}$ を英文字 (英小文字または英大文字) としてください。同じタイミングで配置される $2$ つのブロックには同じ文字を用い、異なるタイミングで配置されるブロックには異なる文字を用いてください。

答えが複数ある場合、どれを出力しても構いません。

サンプル

サンプル1
入力
4 3
...
...
..#
#..
出力
Yes
..a
bba
c..
cdd

ブロックを配置した後、$2$ 行目と $4$ 行目のブロックがすべて削除され、$3$ 行目が $4$ 行目、$1$ 行目が $3$ 行目に移動します。これらの操作を行った後の状態は入力で与えられるものと一致しています。

次のような出力も正解となります。

Yes
oox
..x
X..
XOO
サンプル2
入力
3 3
.#.
.#.
.#.
出力
No

条件を満たすようにブロックを配置することはできません。

サンプル3
入力
10 10
..........
..........
..........
..........
.#.#.#.#.#
#.#.#.#.#.
.#.#.#.#.#
#.#.#.#.#.
.#.#.#.#.#
#.#.#.#.#.
出力
Yes
..........
.b.d.f.h.j
abcdefghij
a.c.e.g.i.
.l.n.p.r.t
klmnopqrst
k.m.o.q.s.
.v.x.z.B.D
uvwxyzABCD
u.w.y.A.C.

サンプル4
入力
4 4
....
.##.
.##.
....
出力
No

操作 (落下) がまだ行える状態であるため、最終的にこのような状態になることはありません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。