UVA639 Don't Get Rooked

在国际象棋中，棋子是一种可以垂直或水平移动任意数量格子的正方形的棋子。在这个问题中，我们将考虑小棋盘（最多4×4），这些棋盘也可能包含棋子无法通过的墙壁。目标是在棋盘上放置尽可能多的棋子，这样就没有两个可以互相接触。棋子的配置如果是合法的，前提是没有两个棋子在同一水平或垂直线上，除非有至少一堵墙壁将这两个棋子隔开。（注：下方“板”均指棋盘） 下面的图片显示了同一块板的五种配置。 第一张是空板，第二张和第三张是合法配置，第四张和第五张是非法配置。 对于这块板 (4x4) 来说，合法配置中的最大棋子数为5；第二张是（配置最大棋子数）一种方法，但或许还有其他几种方法。  您的任务是编写一个程序，在已给出板的长与宽的情况下，计算出在合法配置下可以放置在这块板上的最大棋子数量。

输入文件包含一块或多块板的描述，若后面一行包含数字0，则表示文件结束。每块板的描述都以一行开始，其包含一个正整数n（即板的大小，且n最多为4）。接下来的n行描述了板的每一行，“.”表示可放棋子的空间，大写“X”表示墙。输入文件中没有空格。

对于100%的测试数据： 输出一行，其中包含合法配置在该棋盘上的最大棋子数量。 【由@[bluepaozi](https://www.luogu.com.cn/user/1446141#main)于2024-10-01英译中】