<PREV Problem:
NEXT>
Solved by 246 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

2x1-paving

Time limit = 5 second(s)

Memory limit = 8 Mb

We have square paper N x N. Some cells are black, others are white. Domino-tile is piece of size 2 x 1. The problem is to place maximum number of domino-tiles (pave maximum area) at the paper so that tiles do not overlap and cover only white cells.

Input The first line contains N, 2 ≤ N ≤ 20, Then N lines follow with chars '#' and '.' Char '#' corresponds to black cell, '.' corresponds to white cell.

Output Maximum number of domino-tiles.

Input#1
2
##
#.
Output#1
0
Input#2
2
..
..
Output#2
2
Input#3
3
...
...
..#
Output#3
4

Input#4
4
....
.##.
.##.
....
Output#4
6

Author:
Barsky Eugene & Voroztsov Artem, IV MIPT Contest
11 April 2004

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 54.162.181.75