<PREV Problem:
NEXT>
Solved by 246 users: ...
UserDateAttemptTimeCMSC
fetetriste19 dec 2007C++400.03271 
kia15 jul 2006C++300.02291 
Madiyar_Tktl15 dec 2007C++800.04300 
Madiyar_Tktl15 dec 2007C++100.04307 
Madiyar_Tktl15 dec 2007C++600.04310 
Romka10 jul 2009C++100.01327 
dragonghy14 apr 2007FPC200.01334 
tnndye22 may 2007FPC100.02334 
Philip_PV01 aug 2008C500.23337 
Philip_PV01 aug 2008C++600.08339 
Philip_PV01 aug 2008C++200.07345 
FaLLeNs11 oct 2006C++200.01347 
Philip_PV01 aug 2008C++100.06349 
LoLitter17 oct 2007C++100.02353 
AsukaNoKaze06 jun 2006C++200.03353 
Languages
C++
147
FPC
67
Kylix
16
C
10
Java
8
Python
1
Perl
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 190ms

SW soft NIX
ID = 3.214.224.224