問題一覧 > 通常問題

No.1427 Simplified Tetris

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 28
作問者 : 👑 箱星 / テスター : maspy
お気に入りにしたユーザー ProblemId : 5477 / 自分の提出
問題文最終更新日: 2022-04-26 00:01:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 286 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。