ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2010 > задача:


C. Bishops

Задачи сборника

• A. Providers
• B. Primes
• C. Bishops
• D. Unusual Lottery
• E. Polygons
• F. Liars and Knights
• G. Sequence
• H. Coins
• I. Galls village
• J. String manipulations

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 3000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Кирилл Бутин, ПГУ.

A bishop is a piece in the board game of chess. The bishop has no restrictions in distance for each move, but is limited to diagonal movement, forward and backward.

Consider a chessboard of size NxN.

Your must find the maximum number of bishops that can be placed on the chessboard, such that no pair of bishops can attack each other. Some cells are damaged. Bishops cannot be placed on these cells, but they can attack through them.

Input
The first line contains one integer N (1 ≤ N ≤ 100) - size of the chessboard. The following N lines describe the chessboard. Each line contains N symbols. '.' is entire cell, '#' is damaged.

Output
Output a single integer - the number of bishops that can be placed on the chessboard under the given restrictions.

Input 1 Output 1
2
..
..
2
Input 2 Output 2
2
.#
#.
1

Для отправки решений необходимо выполнить вход.

www.contester.ru