No.1427 Simplified Tetris
Problem Statement
There is a grid with $H$ rows and $W$ columns. Initially, no cell contains a block. The following operation is performed on this grid $0$ or more times.
- Operation (Placement): Choose $2$ adjacent cells (sharing a side) that do not yet contain blocks, and place a block in each of them.
After that, the following operation is performed.
- Operation (Deletion): For each row in which every cell contains a block, delete all the blocks in that row.
After that, the following operation is performed.
- Operation (Fall): When row $i$ contains a block and row $i+1$ contains no block, swap row $i$ and row $i+1$. Repeat this until the operation can no longer be performed.
You are given the state $s$ of the grid after all these operations have been performed. If $s_{ij}$ is ., the cell at row $i$, column $j$ contains no block; if $s_{ij}$ is #, the cell at row $i$, column $j$ contains a block. Find $1$ way of performing the operation (Placement) that achieves this state.
Input
$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$ are integers.
- $s_{ij}$ is
.or#.
Output
If there is no way of performing the operation (Placement) that satisfies the condition, print No.
If there is a way of performing the operation (Placement) that satisfies the condition, print it as follows.
Yes
$t_{11}t_{12}\ldots t_{1W}$
$t_{21}t_{22}\ldots t_{2W}$
$\vdots$
$t_{H1}t_{H2}\ldots t_{HW}$
If no block is placed in the cell at row $i$, column $j$, let $t_{ij}$ be .; if a block is placed there, let $t_{ij}$ be an English letter (lowercase or uppercase). Use the same letter for the $2$ blocks placed at the same time, and use different letters for blocks placed at different times.
If there are multiple answers, you may print any of them.
Sample
Sample 1
Input
4 3 ... ... ..# #..
Output
Yes ..a bba c.. cdd
After the blocks are placed, all the blocks in rows $2$ and $4$ are deleted, row $3$ moves to row $4$, and row $1$ moves to row $3$. The state after these operations matches the one given in the input.
The following output is also accepted.
Yes oox ..x X.. XOO
Sample 2
Input
3 3 .#. .#. .#.
Output
No
It is impossible to place blocks so that the condition is satisfied.
Sample 3
Input
10 10 .......... .......... .......... .......... .#.#.#.#.# #.#.#.#.#. .#.#.#.#.# #.#.#.#.#. .#.#.#.#.# #.#.#.#.#.
Output
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.
Sample 4
Input
4 4 .... .##. .##. ....
Output
No
The operation (Fall) can still be performed in this state, so the final state can never be like this.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
maspy