B. Tetris revisited

Codeforces

IDCF86B

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsgraph matchingsgreedymath

English · Original

Chinese · Translation

Formal · Original

Physicist Woll likes to play one relaxing game in between his search of the theory of everything. Game interface consists of a rectangular _n_ × _m_ playing field and a dashboard. Initially some cells of the playing field are filled while others are empty. Dashboard contains images of all various connected (we mean connectivity by side) figures of 2, 3, 4 and 5 cells, with all their rotations and reflections. Player can copy any figure from the dashboard and place it anywhere at the still empty cells of the playing field. Of course any figure can be used as many times as needed. Woll's aim is to fill the whole field in such a way that there are no empty cells left, and also... just have some fun. Every initially empty cell should be filled with exactly one cell of some figure. Every figure should be entirely inside the board. <center>![image](https://espresso.codeforces.com/13a01b838f7f8abcc4a80e1dd1c019ac72087e2e.png)</center>In the picture black cells stand for initially filled cells of the field, and one-colour regions represent the figures. ## Input First line contains integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 1000) — the height and the width of the field correspondingly. Next _n_ lines contain _m_ symbols each. They represent the field in a natural way: _j_\-th character of the _i_\-th line is "_#_" if the corresponding cell is filled, and "_._" if it is empty. ## Output If there is no chance to win the game output the only number "-1" (without the quotes). Otherwise output any filling of the field by the figures in the following format: each figure should be represented by some digit and figures that touch each other by side should be represented by distinct digits. Every initially filled cell should be represented by "_#_". [samples] ## Note In the third sample, there is no way to fill a cell with no empty neighbours. In the forth sample, Woll does not have to fill anything, so we should output the field from the input.

物理学家 Woll 喜欢在寻找万有理论的过程中玩一款放松的游戏。游戏界面由一个矩形 #cf_span[n × m] 的游戏区域和一个控制面板组成。初始时，游戏区域中的一些格子被填满，其余为空。控制面板包含所有由 2、3、4 和 5 个格子组成的连通（指边连通）图形，包含它们的所有旋转和反射。玩家可以从控制面板复制任意一个图形，并将其放置在游戏区域中仍为空的格子上。当然，每个图形可以使用任意多次。 Woll 的目标是填满整个区域，使得没有空格子留下，同时……享受乐趣。每个初始为空的格子必须被某个图形的恰好一个格子填满。每个图形必须完全位于棋盘内。图中黑色格子代表初始已填满的格子，单色区域代表各个图形。第一行包含整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 1000]）——分别表示游戏区域的高度和宽度。接下来的 #cf_span[n] 行每行包含 #cf_span[m] 个字符，以自然方式表示游戏区域：第 #cf_span[i] 行的第 #cf_span[j] 个字符为 "_#_" 表示对应格子已被填满，为 "_._" 表示为空。如果无法赢得游戏，请仅输出 "-1"（不含引号）。否则，请以如下格式输出任意一种用图形填满区域的方案：每个图形用某个数字表示，且彼此边相邻的图形必须用不同的数字表示。每个初始已填满的格子仍用 "_#_" 表示。在第三个测试用例中，无法填满一个没有空邻居的格子。在第四个测试用例中，Woll 无需填任何格子，因此我们应输出输入中的原始区域。 ## Input 第一行包含整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 1000]）——分别表示游戏区域的高度和宽度。接下来的 #cf_span[n] 行每行包含 #cf_span[m] 个字符，以自然方式表示游戏区域：第 #cf_span[i] 行的第 #cf_span[j] 个字符为 "_#_" 表示对应格子已被填满，为 "_._" 表示为空。 ## Output 如果无法赢得游戏，请仅输出 "-1"（不含引号）。否则，请以如下格式输出任意一种用图形填满区域的方案：每个图形用某个数字表示，且彼此边相邻的图形必须用不同的数字表示。每个初始已填满的格子仍用 "_#_" 表示。 [samples] ## Note 在第三个测试用例中，无法填满一个没有空邻居的格子。在第四个测试用例中，Woll 无需填任何格子，因此我们应输出输入中的原始区域。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 1000 $. Let $ F \in \{ \#, . \}^{n \times m} $ be the input grid, where $ F[i][j] = \# $ denotes a pre-filled cell and $ F[i][j] = . $ denotes an empty cell. Let $ \mathcal{P} $ be the set of all polyominoes of size 2, 3, 4, and 5, including all rotations and reflections. **Constraints** 1. Every empty cell (i.e., where $ F[i][j] = . $) must be covered by exactly one cell of exactly one polyomino from $ \mathcal{P} $. 2. Each polyomino placed must lie entirely within the $ n \times m $ grid. 3. Polyominoes may be used any number of times. 4. Adjacent polyominoes (sharing a side) must be assigned distinct digit labels. 5. Pre-filled cells ($ \# $) remain unchanged and are not part of any placed polyomino. **Objective** Determine if there exists a tiling of all empty cells using polyominoes from $ \mathcal{P} $ such that: - Every empty cell is covered. - No two adjacent polyominoes share the same digit label. If such a tiling exists, output a grid $ G \in (\{ \# \} \cup \{1,2,\dots,9\})^{n \times m} $, where: - $ G[i][j] = \# $ if $ F[i][j] = \# $, - $ G[i][j] \in \{1,2,\dots,9\} $ otherwise, with adjacent polyominoes having distinct digits. If no such tiling exists, output $-1$.

Samples

Input #1

2 3
...
#.#

Output #1

000
#0#

Input #2

3 3
.#.
...
..#

Output #2

5#1
511
55#

Input #3

3 3
...
.##
.#.

Output #3

\-1

Input #4

1 2
##

Output #4

##

API Response (JSON)

{
  "problem": {
    "name": "B. Tetris revisited",
    "description": {
      "content": "Physicist Woll likes to play one relaxing game in between his search of the theory of everything. Game interface consists of a rectangular _n_ × _m_ playing field and a dashboard. Initially some cell",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF86B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Physicist Woll likes to play one relaxing game in between his search of the theory of everything.\n\nGame interface consists of a rectangular _n_ × _m_ playing field and a dashboard. Initially some cell...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "物理学家 Woll 喜欢在寻找万有理论的过程中玩一款放松的游戏。\n\n游戏界面由一个矩形 #cf_span[n × m] 的游戏区域和一个控制面板组成。初始时，游戏区域中的一些格子被填满，其余为空。控制面板包含所有由 2、3、4 和 5 个格子组成的连通（指边连通）图形，包含它们的所有旋转和反射。玩家可以从控制面板复制任意一个图形，并将其放置在游戏区域中仍为空的格子上。当然，每个图形可以使用任意多次...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 1000 $.  \nLet $ F \\in \\{ \\#, . \\}^{n \\times m} $ be the input grid, where $ F[i][j] = \\# $ denotes a pre-filled cell and $ F[i][...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments