{"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":"CF10060F"},"statements":[{"statement_type":"Markdown","content":"Тёмные силы под руководством Саурона заполонили Средиземье, и только Арагорн, сын Араторна, наследник Исилдура и истинный правитель Гондора может найти силы противостоять Тёмному владыке Мордора. Впрочем, мы поможем ему в этом в другой раз, сейчас же давайте оценим, как далеко может зайти Тёмный Властелин.\n\nКарта Средиземья представляет собой клетчатый прямоугольник из N строк по M клеток, каждая из которых может либо полностью принадлежать Саурону, либо полностью не принадлежать. Если в каком-либо квадрате размером 2 × 2 три клетки уже захвачены тёмными силами, то они способны захватить и четвёртую клетку.\n\nИзначально полчищам Саурона уже подвластны некоторые клетки на карте Средиземья. Оцените, сколько клеток может оказаться под его контролем в худшем случае.\n\nПервая строка входного файла содержит два целых числа N и M (1 ≤ N, M ≤ 40) — количество строк и столбцов на карте Средиземья. Следующие N строк по M символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘_._’ соответствует клетке карты, свободной от власти Саурона, а ‘_#_’ — клетке, захваченной Сауроном. Строки нумеруются от 1 до N, столбцы — от 1 до M.\n\nВ выходной файл выведите одно число — максимальное количество клеток, которые могут контролировать тёмные силы после всех завоеваний.\n\n## Входные Данные\n\nПервая строка входного файла содержит два целых числа N и M (1 ≤ N, M ≤ 40) — количество строк и столбцов на карте Средиземья. Следующие N строк по M символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘_._’ соответствует клетке карты, свободной от власти Саурона, а ‘_#_’ — клетке, захваченной Сауроном. Строки нумеруются от 1 до N, столбцы — от 1 до M.\n\n## Выходные Данные\n\nВ выходной файл выведите одно число — максимальное количество клеток, которые могут контролировать тёмные силы после всех завоеваний.\n\n## Примеры\n\nВходные данные2 2###.Выходные данные4Входные данные3 4#...#...###.Выходные данные9Входные данные3 5...###....#.#..Выходные данные5\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"CF10060F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}