火力配置网络 ## 来源 Zhejiang University Local Contest 2001; Mid-Central USA 1998 (ZOJ1002, POJ1315) ## 题目描述 假定有一个方形的城市，街道都是直的。城市的地图是一个n行n列的方形棋盘，每行每列代表一条街道或一堵墙。城市中有碉堡，每个碉堡有4个开口，可以射击。这4个开口分别朝北、东、南和西。每个开口都有一挺机关枪朝外射击。假定子弹是如此厉害，射程可以达到任意远的距离，也可以摧毁该方向上的碉堡。而城市中的墙筑得是如此结实以至于可以抵挡子弹。 本题的目标是要在城市中放置尽可能多的碉堡，并且保证碉堡之间互相不会摧毁。碉堡放置的方案如果是合法的，必须保证任何两个碉堡不在同一行、同一列，除非它们之间至少有一堵墙隔开。在本题中，我们考虑的城市都比较小，至多4×4大小。 下图给出了同一个地图的5种碉堡放置的情形。第1幅图是空的地图，第2、3幅图是合理的放置方案，而第4、5幅图是不合理的放置方案。在这个地图中，最多能放置5个碉堡。第2幅图显示了放置5个碉堡的一种方法，但也存在其他方法可以放置5个碉堡。  你的任务是编写程序，给定地图的描述，计算能在该地图中合理地放置碉堡的最大数目。 ## 输入描述 输入文件包含多个地图的描述。最后一行为0，代表输入结束。每个地图描述的第1行是一个正整数n，表示城市的大小；n至多为4。接下来n行描述了地图，地图中允许出现的符号及其含义如下：'.'，代表空地；'X'，代表墙。输入文件中没有空格。 ## 输出描述 对每个地图描述，输出一行，为一个整数，表示能在该地图中合理的放置碉堡的最大数目。 ## 样例输入 ```txt 4 .X.. .... XX.. .... 0 ``` ## 样例输出 ```txt 5 ```