{"problem":{"name":"C. Explode 'Em All","description":{"content":"The prime minister of Berland decided to build a new city in the country. It's hard to describe the excitement of all Berland citizens, but indeed this is great news from the economic, social and cult","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10124C"},"statements":[{"statement_type":"Markdown","content":"The prime minister of Berland decided to build a new city in the country. It's hard to describe the excitement of all Berland citizens, but indeed this is great news from the economic, social and cultural standpoints.\n\nThe land in Berland is occupied almost entirely and it's very hard to find free space for construction, so it was decided to build the city on a stony terrain. The map of this terrain is represented as an n × m grid, where each cell of the grid is either an empty space or a rock.\n\nOf course, before construction is started, the given terrain must be completely cleared from rocks. As you may guess, you were hired to complete this mission. Your goal is to destroy all rocks by dropping bombs from a plane. A bomb can be dropped on any cell of the map, and you are free to select where you want to drop each bomb. When a bomb targeted for cell (i, j) reaches the ground, it destroys all rocks in row i and also all rocks in column j of the grid. If cell (i, j) contains a rock, this rock is also destroyed.\n\nPlease help the prime minister of Berland to find the minimum number of bombs required to completely clear the given terrain from rocks.\n\nThe first line of input contains two integers n and m (1 ≤ n, m ≤ 25) — the number of rows and columns correspondingly. Each of the next n lines contains m characters describing the terrain. An empty space is denoted by \"_._\", while a rock is denoted by \"_*_\".\n\nWrite a single integer to the output — the minimum numbers of bombs required for destroying all rocks on the terrain.\n\nIn the first sample test it's only required to drop 2 bombs from a plane: one bomb to cell (2,2) and another bomb to cell (6, 10). Row and column indices in this explanation are 1-based.\n\n## Input\n\nThe first line of input contains two integers n and m (1 ≤ n, m ≤ 25) — the number of rows and columns correspondingly. Each of the next n lines contains m characters describing the terrain. An empty space is denoted by \"_._\", while a rock is denoted by \"_*_\".\n\n## Output\n\nWrite a single integer to the output — the minimum numbers of bombs required for destroying all rocks on the terrain.\n\n[samples]\n\n## Note\n\nIn the first sample test it's only required to drop 2 bombs from a plane: one bomb to cell (2,2) and another bomb to cell (6, 10). Row and column indices in this explanation are 1-based.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the grid, with $ 1 \\leq n, m \\leq 25 $.  \nLet $ G \\in \\{ \\text{.}, \\text{*} \\}^{n \\times m} $ be the grid, where $ G_{i,j} = \\text{*} $ indicates a rock at position $ (i,j) $, and $ G_{i,j} = \\text{.} $ indicates an empty space.  \nLet $ R \\subseteq \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the set of rock positions:  \n$$ R = \\{ (i,j) \\mid G_{i,j} = \\text{*} \\} $$\n\n**Constraints**  \n- Each bomb dropped at position $ (i,j) $ destroys all rocks in row $ i $ and column $ j $.  \n- The goal is to cover all rock positions using the minimum number of such row-column bomb operations.\n\n**Objective**  \nFind the minimum number of bombs $ k \\in \\mathbb{Z}^+ $ such that there exists a set of bomb positions $ B = \\{ (i_1, j_1), \\dots, (i_k, j_k) \\} $ satisfying:  \n$$ \\bigcup_{(i,j) \\in B} \\left( \\{i\\} \\times \\{1,\\dots,m\\} \\cup \\{1,\\dots,n\\} \\times \\{j\\} \\right) \\supseteq R $$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10124C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}