假定我们有一个城市广场直街上. 地图是城市的一个广场,董事会与N行和N个栏目, 代表每一条街道或一片墙. 一个碉堡是一个小城堡,有四个开口通过它拍摄. 四是挖掘面临北,东,南,西,分别. 会有一个机枪射击通过每个开幕式. 这里我们假设一颗子弹是如此强大,它可以穿越任何距离和摧毁一座碉堡 开展起来. 在另一方面,一个墙是如此强烈,建成了可以阻挡子弹. 其目标是把许多碉堡在一个城市尽可能使没有两个可以摧毁每 其他. 一个配置的碉堡,是法律规定的,没有任何两个碉堡都在同一横列或立柱 在地图上,除非至少有一个隔离墙. 在这个问题,我们会考虑小城市广场(最多4 × 4 )含有墙壁透过子弹不能运行 通过. 以下图像显示图片五的同一局. 第一幅是空局,但第二和第三图片法律配置 而第四次和第五次作品展的非法配置. 这一局,最多碉堡在法律配置五日; 第二图示做的一个方法,但是还有其他一些方式. 你的任务是写一个节目中说,鉴于地描述了一个图, 算出最多碉堡可以放置在该市的法律配置. 输入文件包含一个或多个地图说明 其次是一条线含有数字0 ,信号结束的档案. 每个地图开始,描述了线路含有一个正整数n ,是规模的城市; 氮将大部分4 . 未来线上形容每一个连续的地图, 与' . '显示一个开放的空间和一个大写的'十大'显示墙. 有没有空间的输入文件. 每个测试案例, 生产一线含有最多碉堡可以放置在该市的法律配置. 样例输入:
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 piece 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.
一个碉堡如同一小城堡,在这个城堡的四周有四个开口用以射击。这四个开口分别面向北,东,南和西。
There will be one machine gun shooting through each opening.
从每一个开口处都有一部机枪以射击。
Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way.
在此,我们假设有一种力量及其强大的子弹,有无限的射程,在发射的过程中会摧毁它所经过的碉堡。
On the other hand, a wall is so strongly built that can stop the bullets.
那么另一方面,我们就需要有一面坚硬的足以阻挡这些子弹的墙。
The goal is to place as many blockhouses in a city as possible so that no two can destroy each other.
我们的目标是在城市里尽可能多地设置碉堡,使每两个互相之间无法进行破坏。
A configuration of blockhouses is legal provided that 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 which bullets cannot run through.
对于这一问题,我们会考虑设有防弹墙的小型方形城市。(不得大于4*4)
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 board, the maximum number of blockhouses in a legal configuration is 5; the second 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, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.
在这一版块中,法定构造的碉堡数目最多为5;第二幅图就显示了做到这一点的一种方法,但还有其他一方法。你的任务是编写一个程序,以描述这幅地图并计算出在法定构造中,所能在这一程式设置的最多的碉堡数。
The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file.
输入的文件当包括一个或更多的地图描述,并在每一文件下划出一条末端标有数字0的直线,以标志着文件的结束。
Each map description begins with a line containing a positive integer n that is the size of the city; 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.
每一幅地图描述以一条标有确切的整数n(这一数字表示的是城市的大小,不得大于4)的直线为起点。其余的n条线都分别表示地图的经线,经线上的“.”表示开放的空间,大写的“X”则表示墙。
There are no spaces in the input file. For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration. Sample input:
在输入的文件中不得有空的地方。对于每一个测试案例,生产一线含有最多碉堡可以放置在该市的法律配置. 样例输入: