<ПРЕД Задача:
СЛЕД>
Задачу решили 246 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Замощение доминошками

Time limit = 5 секунд(ы)

Memory limit = 8 Mb

Из клеточного листка N x N вырезали некоторые клетки. Есть доминошки — плитки размера 2 x 1. Задача: заполните оставшийся лист доминошками, а если его невозможно заполнить целиком, положите на него максимальное число доминошек (каждая доминошка занимает две соседние клетки листка).

Вход В первой строчке указано число N, 2 ≤ N ≤ 20, А затем идут N строчек по N символов '#' или '.' Знак '#' означает, что соответствующая клетка листа вырезана.

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

Вход#1
2
##
#.
Выход#1
0
Вход#2
2
..
..
Выход#2
2
Вход#3
3
...
...
..#
Выход#3
4

Вход#4
4
....
.##.
.##.
....
Выход#4
6

Автор:
Барский Евгений и Ворожцов Артем, IV Физтех олимпиада
11 апреля 2004

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.214.224.224