1483: Блокування королів


Submit solution


Points:20
Time limit:1.0s
Memory limit:500M
Author:

Problem types

Граючи в шахи на рiзних турнiрах, Марта декiлька разiв програла партiю пiд час турових ендшпiлiв. На тренуваннях, про розглядi рiзних турових розкладок, у неї виникла iдея такої задачi. На шаховiй дошцi розмiрнiстю N x M Марта розмiстила K королiв. Тепер треба розмiстити мiнiмальну кiлькiсть тур так, щоб виконувалися наступнi умови:

  • жоден король не знаходиться пiд боєм тури;

  • кожен король iзольований, тобто вiн не може дiйти до iншого короля, щоб не перетнути поле пiд боєм тури або взявши туру.

Допоможiть Мартi перевiрити свої розв’язки: напишiть програму, яка визначить необхiдну мiнiмальну кiлькiсть тур. Обмеження:

1 <= N, M <= 1024

N · M <= 1024

Пояснення

Наприклад, туру можна розмiстити так:

........
........
..K.....
......K.
........
...T....
.K..K...
........

Формат вхідних даних

Перший рядок вхiдного потоку мiстить два цiлих додатних числа N i M , роздiлених пропуском. Наступнi N рядкiв описують шахову дошку. Кожен iз цих рядкiв мiстить рядок довжиною M , який мiстить символи ’.’ i ’K’, що позначають вiдповiдно порожню клiтину та клiтину iз королем.

Формат вихідних даних

Виведiть мiнiмальну кiлькiсть тур для блокування королiв або -1, якщо це зробити неможливо.

Приклад вхідних даних

8 8
........
........
..K.....
......K.
........
........
.K..K...
........

Приклад вихідних даних

1

Comments

There are no comments at the moment.