{"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 single dots (\".\").\n\nYou 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.\n\nThe 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).\n\nThe 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.\n\nOutput a single positive integer $k$: the number of spaces in the dungeon accessible from your starting space, according to the rules above.\n\n## Input\n\nThe 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.\n\n## Output\n\nOutput a single positive integer $k$: the number of spaces in the dungeon accessible from your starting space, according to the rules above.\n\n[samples]","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- An edge exists between $ (i, j) $ and $ (i', j') $ iff $ |i - i'| + |j - j'| = 1 $ and both cells are not walls.  \n\nLet $ W \\subseteq V $ be the set of wall cells: $ W = \\{ (i, j) \\mid G[i][j] = \\text{'X'} \\} $.  \nLet $ S = (0, 0) $ be the starting cell (top-left corner).  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq \\text{some upper bound (implied by input)} $  \n2. $ S \\notin W $ (starting cell is not a wall)  \n3. Movement is restricted to four cardinal directions; no diagonal moves.  \n4. Movement is prohibited through $ W $ or outside the grid boundaries.  \n\n**Objective**  \nCompute the size of the connected component of $ V \\setminus W $ containing $ S $:  \n$$\nk = \\left| \\{ v \\in V \\setminus W \\mid \\text{there exists a path from } S \\text{ to } v \\text{ in } G \\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269195","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}