F. Средиземье в опасности

Codeforces

IDCF10059F

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Тёмные силы под руководством Саурона заполонили Средиземье, и только Арагорн, сын Араторна, наследник Исилдура и истинный правитель Гондора, может найти силы противостоять Тёмному владыке Мордора. Впрочем, ему мы поможем в другой раз, сейчас же давайте оценим, как далеко может зайти Тёмный Властелин. Карта Средиземья представляет собой клетчатый прямоугольник из N строк по M клеток, каждая из которых может либо полностью принадлежать Саурону, либо полностью не принадлежать. Если в любом квадрате размером 2 × 2 три клетки уже захвачены тёмными силами, то они могут завоевать четвёртую клетку этого квадрата. Изначально полчищам Саурона подвластно некоторое множество клеток карты Средиземья. Оцените максимальное количество клеток, которое они могут подвести под его контроль. В первой строке содержатся два целых числа N и M (1 ≤ N, M ≤ 1 000) — количество строк и столбцов на карте Средиземья. Следующие N строк по M символов описывают клетки карты. Символ ‘_._’ соответствует клетке карты, свободной от власти Саурона, а ‘_#_’ — клетке, захваченной Сауроном. Строки нумеруются от 1 до N, столбцы — от 1 до M. Выведите единственное число — максимальное количество клеток, которые могут контролировать тёмные силы после всех завоеваний. ## Входные Данные В первой строке содержатся два целых числа N и M (1 ≤ N, M ≤ 1 000) — количество строк и столбцов на карте Средиземья.Следующие N строк по M символов описывают клетки карты. Символ ‘_._’ соответствует клетке карты, свободной от власти Саурона, а ‘_#_’ — клетке, захваченной Сауроном. Строки нумеруются от 1 до N, столбцы — от 1 до M. ## Выходные Данные Выведите единственное число — максимальное количество клеток, которые могут контролировать тёмные силы после всех завоеваний. ## Примеры Входные данные2 2###.Выходные данные4Входные данные3 4#...#...###.Выходные данные9Входные данные3 5...###....#.#..Выходные данные5 [samples]

**Definitions** Let $ N, M \in \mathbb{Z} $ be the dimensions of the grid, with $ 1 \leq N, M \leq 1000 $. Let $ G \in \{0,1\}^{N \times M} $ be the grid, where $ G[i][j] = 1 $ if cell $ (i,j) $ is initially controlled by Sauron, and $ G[i][j] = 0 $ otherwise. **Constraints** A cell $ (i,j) $ can be captured if there exists a $ 2 \times 2 $ subgrid centered at or including $ (i,j) $ such that exactly three of its four cells are already controlled (i.e., value 1). Capture propagates iteratively: once a cell is captured, it may enable further captures. **Objective** Compute the maximum number of cells that can be controlled by Sauron after applying the capture rule repeatedly until no more captures are possible. That is, find the size of the closure of the initial set under the rule: > If in any $ 2 \times 2 $ subgrid, three cells are 1, then the fourth becomes 1. Formally, let $ C \subseteq \{1,\dots,N\} \times \{1,\dots,M\} $ be the initial set of controlled cells. Let $ \overline{C} $ be the smallest superset of $ C $ such that for every $ 2 \times 2 $ subgrid $ S $, if $ |S \cap \overline{C}| = 3 $, then the fourth cell of $ S $ is also in $ \overline{C} $. Output $ |\overline{C}| $.

API Response (JSON)

{
  "problem": {
    "name": "F. Средиземье в опасности",
    "description": {
      "content": "Тёмные силы под руководством Саурона заполонили Средиземье, и только Арагорн, сын Араторна, наследник Исилдура и истинный правитель Гондора, может найти силы противостоять Тёмному владыке Мордора. Впр",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10059F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Тёмные силы под руководством Саурона заполонили Средиземье, и только Арагорн, сын Араторна, наследник Исилдура и истинный правитель Гондора, может найти силы противостоять Тёмному владыке Мордора. Впр...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, M \\in \\mathbb{Z} $ be the dimensions of the grid, with $ 1 \\leq N, M \\leq 1000 $.  \nLet $ G \\in \\{0,1\\}^{N \\times M} $ be the grid, where $ G[i][j] = 1 $ if cell $ (i,j) $ i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments