Розташування антени#6819
Глобальному аеронавігаційному науково-дослідному центру доручено побудувати мережу мобільного зв'язку п'ятого покоління у Швеції. Вони отримали це завдання завдяки розробці нової, дуже ефективної антени під назвою 4DAir, яка представлена в чотирьох типах. Кожен тип антени може передавати і приймати сигнали лише в напрямку, що відповідає (трохи зміщеній) широтній і довготній сітці через взаємодіюче електромагнітне поле Землі. Ці чотири типи відповідають напрямкам північ, захід, південь і схід. Нижче наведено приклад зображення з дванадцятьма маленькими кільцями, що позначають цікаві місця, і дев'ятьма антенами 4DAir, зображеними еліпсами, які їх покривають.
Очевидно, що бажано використовувати якомога менше антен, але при цьому потрібно забезпечити покриття для кожного об'єкта інтересу. Задачу можна сформулювати так: нехай - прямокутна матриця, що описує поверхню Швеції, де кожна точка є або точкою інтересу, яка повинна бути покрита хоча б однією антеною, або порожнім місцем. Антени можна розміщувати в будь-якому місці матриці . Коли антена розміщується в рядку і стовпці , ця точка вважається покритою, а також покривається одна з сусідніх точок: (c + 1, r), (c, r + 1), (c - 1, r) або (c, r - 1) залежно від типу антени. Яка найменша кількість антен потрібна, щоб покрити всі точки інтересу в матриці ?
Перший рядок містить кількість сценаріїв . Кожен сценарій починається з рядка, що містить два натуральних числа і (1 < h < 40, 0 < w < 10). Далі задана матриця з рядків, кожен з яких містить символів з набору [*, o]. Символ * позначає точку інтересу, тоді як символ o представляє відкритий простір.
Для кожного сценарію в окремому рядку виведіть мінімальну кількість антен, необхідних для покриття всіх *-елементів у матриці сценарію.
Приклад 1