Алгоритмы

Атакуючі тури
Красиві шахові задачі є поширеним джерелом вправ з алгоритмів. Починаючи з відомої задачі про 8 ферзів, було зроблено кілька узагальнень і варіацій. Одна з них - завдання про n тур, що складається в розташуванні n тур на шахівниці розміру n на n так, щоб вони не били одна одну.

Професор Ананд презентував завдання про n тур перед студентами. Так як тури б'ють одна одну тільки коли вони знаходяться на одній горизонталі або вертикалі, студенти швидко знайшли розвязок, поставивши всі тури на головній діагоналі. Професор вирішив ускладнити завдання, додавши на дошку кілька пішаків, дві тури б'ють одна одну тільки якщо вони знаходяться на одній вертикалі або горизонталі, і при цьому між ними немає пішаків. Оскільки пішаки займають певні поля, то у тур з'являються обмеження на клітини, куди їх можна поставити.

За розміром дошки і розташуванню пішаків вкажіть професору Ананду максимальну кількість тур, які можна поставити на порожніх клітинах так, щоб вони не били одна одну.

Вхідні дані
Перший рядок містить число n (1 ≤ n ≤ 100) - кількість рядків і стовпців на дошці. Кожен з таких n рядків містить n символів. В i - му рядку * j * - перший символ вказує на вміст у * i * - го рядка і * j * - ї колонки дошки. Символом може бути або "." (точка) або буква верхнього регістру "X", що вказують на відповідно порожню клітину або клітку з пішаком.

Вихідні дані
Виведіть максимальну кількість тур, які можна поставити на порожніх клітинах так, щоб вони не били одна одну.


Ліміт часу 1 секунда

Ліміт використання пам'яті 64 MiB
Вхідні дані #1
1
X
Вихідні дані #1
0
Вхідні дані #2
5
X....
X....
..X..
.X...
....X
Вихідні дані #2
7
Вхідні дані #3
4
....
.X..
....
....
Вихідні дані #3
5


ПОМОГИТЕ С ЗАДАЧЕЙ ПОЖАЛУЙСТА

0

Официальными языками форума являются русский и английский языки. Размещение сообщений на других языках запрещено.

0

	Комментарий модератора
	Пункт 1.4 правил форума Закрыто.

0