Зона висадки
Місії з евакуації та збору постачань регулярно виконуються спеціальними командами. Одним із перших завдань цих місій є встановлення периметру з барикадами. Барикади є дорогими і потребують часу для встановлення, тому важливо зменшити їх кількість, необхідну для блокування території.
Вам буде надано кілька карт зон високого інтересу для скидання. Ваше завдання — написати програму, яка визначить мінімальну кількість барикад, необхідних для кожної зони скидання.
Зомбі почнуть свій підхід ззовні карти, тому будь-яка відкрита ділянка на кордоні доступна для зомбі. Барикади можуть бути розміщені між будь-якими двома суміжними відкритими ділянками (включаючи зону скидання), щоб заблокувати рух зомбі. Усі зони за межами карти слід вважати відкритими ділянками.
Ось приклад однієї з карт, які вам будуть надані:
XXX..XXX
XXX..XXX
.....XXX
XXX..XXX
XDDDD.XX
XDDDD...
XXXXXXXX
Легенда:
Приклад конфігурації барикад:
Рішення: 3
Вхідні дані
Перше число, N (1 ≤ N ≤ 20), вказує кількість карт. Для кожної карти буде два параметри, R та C (1 ≤ R, C ≤ 150), що позначають кількість рядків та стовпців на карті, за якими слідує сама карта, як описано вище. Кожен рядок буде на своєму рядку, і всі рядки матимуть однакову кількість символів, рівну C.
Вихідні дані
Для кожної карти виведіть один рядок, що містить мінімальну кількість барикад, необхідних для блокування зони скидання.