A. Treasure Island

Codeforces

IDCF10097A

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Pirate John Silver has found a map depicting exactly one island in a sea. The map is a piece of cloth divided into cells: n cells in height and m cells in width. John Silver knows that every cell denotes either land or water, but some of the cells are erased, and now it's absolutely impossible to say what these cells represent. Help John Silver to restore the map of the island. An island is a non-empty set of land cells connected in four directions (up, down, left and right). The first line contains two integers n and m (1 ≤ n, m ≤ 50) — the sizes of the map. Each of the next n lines contains m characters and describes the map. A character is equal to «_#_» if this cell is a water cell, «_._» if it's a land cell, and «_?_» if this cell is erased. It's guaranteed that the input contains at least one character «_._» and at least one character «_?_». If it's not possible to restore the map so that it would depict exactly one island, output «_Impossible_». If the map can be restored in a unique way, output n lines of m characters in the same format as they are in the input, but replacing «_?_» with «_._» or «_#_». And if there are several correct ways to restore the map, output «_Ambiguous_». ## Input The first line contains two integers n and m (1 ≤ n, m ≤ 50) — the sizes of the map.Each of the next n lines contains m characters and describes the map. A character is equal to «_#_» if this cell is a water cell, «_._» if it's a land cell, and «_?_» if this cell is erased.It's guaranteed that the input contains at least one character «_._» and at least one character «_?_». ## Output If it's not possible to restore the map so that it would depict exactly one island, output «_Impossible_».If the map can be restored in a unique way, output n lines of m characters in the same format as they are in the input, but replacing «_?_» with «_._» or «_#_».And if there are several correct ways to restore the map, output «_Ambiguous_». [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 50 $. Let $ M \in \{ \texttt{\#}, \texttt{.}, \texttt{?} \}^{n \times m} $ be the input grid, where: - $ \texttt{\#} $ denotes *water* (fixed), - $ \texttt{.} $ denotes *land* (fixed), - $ \texttt{?} $ denotes *erased* (unknown). Let $ L = \{ (i,j) \mid M[i][j] = \texttt{.} \} $ be the set of fixed land cells. Let $ E = \{ (i,j) \mid M[i][j] = \texttt{?} \} $ be the set of erased cells. An *island* is a non-empty, 4-connected component of land cells. **Constraints** 1. $ L \neq \emptyset $ and $ E \neq \emptyset $ (guaranteed). 2. Each erased cell $ (i,j) \in E $ must be assigned either $ \texttt{.} $ (land) or $ \texttt{\#} $ (water). 3. The resulting grid must contain **exactly one** connected island (i.e., exactly one 4-connected component of land cells, and all other cells are water). 4. All fixed land cells $ L $ must belong to this single island. **Objective** Determine the number of valid assignments $ f: E \to \{ \texttt{.}, \texttt{\#} \} $ such that: - The set $ L \cup f^{-1}(\texttt{.}) $ forms a single 4-connected component. - All other cells (i.e., $ \texttt{\#} $ and $ f^{-1}(\texttt{\#}) $) are not part of any land component. Then: - If **zero** such assignments exist → output `"Impossible"`. - If **exactly one** such assignment exists → output the grid with `?` replaced by the assigned value. - If **two or more** such assignments exist → output `"Ambiguous"`.

API Response (JSON)

{
  "problem": {
    "name": "A. Treasure Island",
    "description": {
      "content": "Pirate John Silver has found a map depicting exactly one island in a sea. The map is a piece of cloth divided into cells: n cells in height and m cells in width. John Silver knows that every cell deno",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Pirate John Silver has found a map depicting exactly one island in a sea. The map is a piece of cloth divided into cells: n cells in height and m cells in width. John Silver knows that every cell deno...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 50 $.  \nLet $ M \\in \\{ \\texttt{\\#}, \\texttt{.}, \\texttt{?} \\}^{n \\times m} $ be the input grid, where:  \n- $ \\texttt{\\#} $ denot...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments