195. Dungeon

Codeforces

IDCF10269195

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Unfortunately, you find yourself trapped in a dungeon, which can be represented as a 2D grid. The dungeon contains some impassable walls, represented by X characters, and empty space, represented as single dots ("."). You start in the top left corner. You want to figure out how many cells are accessible from your starting space. You can move up, down, right, and left any number of times, but you cannot move diagonally, and you cannot move through walls. You also can't go off the board. The first line of input consists of a single positive integer $n$: the number of rows and columns of the dungeon (the dungeon is always square). The next $n$ lines each contain $n$ characters: the grid representation of the dungeon. If a character is an "X", it represents an impassable wall, and if a character is a single dot, it represents empty space. Output a single positive integer $k$: the number of spaces in the dungeon accessible from your starting space, according to the rules above. ## Input The first line of input consists of a single positive integer $n$: the number of rows and columns of the dungeon (the dungeon is always square).The next $n$ lines each contain $n$ characters: the grid representation of the dungeon. If a character is an "X", it represents an impassable wall, and if a character is a single dot, it represents empty space. ## Output Output a single positive integer $k$: the number of spaces in the dungeon accessible from your starting space, according to the rules above. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the dimension of the square grid. Let $ G = (V, E) $ be a grid graph where: - $ V = \{ (i, j) \mid 0 \leq i, j < n \} $ is the set of grid cells. - An edge exists between $ (i, j) $ and $ (i', j') $ iff $ |i - i'| + |j - j'| = 1 $ and both cells are not walls. Let $ W \subseteq V $ be the set of wall cells: $ W = \{ (i, j) \mid G[i][j] = \text{'X'} \} $. Let $ S = (0, 0) $ be the starting cell (top-left corner). **Constraints** 1. $ 1 \leq n \leq \text{some upper bound (implied by input)} $ 2. $ S \notin W $ (starting cell is not a wall) 3. Movement is restricted to four cardinal directions; no diagonal moves. 4. Movement is prohibited through $ W $ or outside the grid boundaries. **Objective** Compute the size of the connected component of $ V \setminus W $ containing $ S $: $$ k = \left| \{ v \in V \setminus W \mid \text{there exists a path from } S \text{ to } v \text{ in } G \} \right| $$

API Response (JSON)

{
  "problem": {
    "name": "195. Dungeon",
    "description": {
      "content": "Unfortunately, you find yourself trapped in a dungeon, which can be represented as a 2D grid. The dungeon contains some impassable walls, represented by X characters, and empty space, represented as s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269195"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Unfortunately, you find yourself trapped in a dungeon, which can be represented as a 2D grid. The dungeon contains some impassable walls, represented by X characters, and empty space, represented as s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the dimension of the square grid.  \nLet $ G = (V, E) $ be a grid graph where:  \n- $ V = \\{ (i, j) \\mid 0 \\leq i, j < n \\} $ is the set of grid cells.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments