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