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