eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Атакуючі тури

Атакуючі тури

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
1
X
Вихідні дані #1
0
Вхідні дані #2
5
X....
X....
..X..
.X...
....X
Вихідні дані #2
7
Вхідні дані #3
4
....
.X..
....
....
Вихідні дані #3
5
Автор Pablo Ariel Heiber
Джерело 2013 South America, Latino America, Задача А