eolymp
bolt
Try our new interface for solving problems
Məsələlər

Атакующие ладьи

Атакующие ладьи

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

Профессор Ананд презентовал задачу об n ладьях перед студентами. Так как ладьи бьют друг друга только когда они находятся на одной горизонтали или вертикали, студенты быстро нашли решение, поставив все ладьи на главной диагонали. Профессор решил усложнить задачу, добавив на доску несколько пешек, две ладьи бьют друг друга только если они находятся на одной вертикали или горизонтали, и при этом между ними нет пешек. Поскольку пешки занимают определенные поля, то у ладей появляются ограничения на клетки, куда их можно поставить.

По размеру доски и расположению пешек укажите профессору Ананду максимальное количество ладей, которое можно поставить на пустых клетках так, чтобы они не били друг друга.

Giriş verilənləri

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

Çıxış verilənləri

Выведите максимальное количество ладей, которое можно поставить на пустых клетках так чтобы они не били друг друга.

Nümunə

Giriş verilənləri #1
1
X
Çıxış verilənləri #1
0
Giriş verilənləri #2
5
X....
X....
..X..
.X...
....X
Çıxış verilənləri #2
7
Giriş verilənləri #3
4
....
.X..
....
....
Çıxış verilənləri #3
5
Mənbə 2013 South America , Latino America, Задача А