Algorithm 版 (精华区)

发信人: Lerry (life is waiting...), 信区: Algorithm
标  题: 1002P-FireNet-ZJU
发信站: 哈工大紫丁香 (2002年10月05日22:29:09 星期六), 站内信件

Fire Net
----------------------------------------------------------------------------
----
Time limit: 1 Seconds   Memory limit: 32768K
Total Submit: 785   Accepted Submit: 255
----------------------------------------------------------------------------
----
Suppose that we have a square city with straight streets. A map of a city is
 a square board with n rows and n columns, each representing a street or a p
iece of wall.
A blockhouse is a small castle that has four openings through which to shoot
. The four openings are facing North, East, South, and West, respectively. T
here will be one machine gun shooting through each opening.
Here we assume that a bullet is so powerful that it can run across any dista
nce and destroy a blockhouse on its way. On the other hand, a wall is so str
ongly built that can stop the bullets.
The goal is to place as many blockhouses in a city as possible so that no tw
o can destroy each other. A configuration of blockhouses is legal provided t
hat no two blockhouses are on the same horizontal row or vertical column in 
a map unless there is at least one wall separating them. In this problem we 
will consider small square cities (at most 4x4) that contain walls through w
hich bullets cannot run through.
The following image shows five pictures of the same board. The first picture
 is the empty board, the second and third pictures show legal configurations
, and the fourth and fifth pictures show illegal configurations. For this bo
ard, the maximum number of blockhouses in a legal configuration is 5; the se
cond picture shows one way to do it, but there are several other ways.
Your task is to write a program that, given a description of a map, calculat
es the maximum number of blockhouses that can be placed in the city in a leg
al configuration.
The input file contains one or more map descriptions, followed by a line con
taining the number 0 that signals the end of the file. Each map description 
begins with a line containing a positive integer n that is the size of the c
ity; n will be at most 4. The next n lines each describe one row of the map,
 with a '.' indicating an open space and an uppercase 'X' indicating a wall.
 There are no spaces in the input file.
For each test case, output one line containing the maximum number of blockho
uses that can be placed in the city in a legal configuration.
Sample input:
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
Sample output:
5
1
5
2
4

--
２、这个世界不会在乎你的自尊，而是期望你先做出成绩，

再去强调自己的感觉。

                                     ——比尔·盖茨

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.249.231]