1 /*
 2     本题大意：给出一个n * n的矩阵，让你在这个矩阵中放置尽可能多的炮台。
 3     放置炮台的规则为，任意两个炮台都不在同一行同一列，除非他们之间有wall。
 4     
 5     本题思路：这题很明显回溯可以做，但是下面我们用二分匹配讲解一下这个题，
 6     很明显我们知道如果一个点被选取，那么和他在同一行或者同一列的中间不存
 7     在wall的所有点都不能被选取，所以我们就可以考虑如何限制？我们可以把
 8     这个图按照行缩点，再按照列缩点，那么我们就可以知道，对于缩点之后的行
 9     标号i和列标号j，如果i -> j之间存在一条边，那就说明在方格(i, j)上放了
10     一个点，那么i行j列不能再放其它其它点，那么我们可以想到对得到的缩点进行
11     建立二分图，行和列分别为二部图的两部分，然后依据原图建边，寻找到最大匹配
12     即为答案。
13 */
14 #include <cstdio>
15 #include <cstring>
16 #include <algorithm>
17 using namespace std;
18 
19 const int maxn = 20 + 5;
20 bool used[maxn];//表示是否在交错路中
21 int linker[maxn];//存储匹配点
22 int g[maxn][maxn];//存缩点之后的图
23 char str[maxn][maxn];
24 int x[maxn][maxn], cntx;//行点集
25 int y[maxn][maxn], cnty;//列点集
26 
27 bool dfs(int u) {
28     for(int v = 1; v <= cnty; v ++) {
29         if(g[u][v] && !used[v]) {
30             used[v] = true;
31             if(linker[v] == -1 || dfs(linker[v])) {
32                 linker[v] = u;
33                 return true;
34             }
35         }
36     }
37     return false;
38 }
39 
40 int hungary() {
41     int res = 0;
42     memset(linker, -1, sizeof linker);
43     for(int u = 1; u <= cntx; u ++) {
44         memset(used, false, sizeof used);
45         if(dfs(u)) res ++;
46     }
47     return res;
48 }
49 
50 int main() {
51     int n;
52     while(scanf("%d", &n) && n) {
53         memset(x, 0, sizeof x);
54         memset(y, 0, sizeof y);
55         memset(g, false, sizeof g);
56         for(int i = 0; i < n; i ++) {
57             scanf("%s", str[i]);
58         }
59         cntx = 1;
60 
61         //对行缩点
62         for(int i = 0; i < n; i ++) {
63             for(int j = 0; j < n; j ++) {
64                 if(str[i][j] == ‘.‘) x[i][j] = cntx;
65                 if(str[i][j] == ‘X‘) cntx ++;
66             }
67             cntx ++;
68         }
69 
70         //对列缩点
71         cnty = 1;
72         for(int j = 0; j < n; j ++) {
73             for(int i = 0; i < n; i ++) {
74                 if(str[i][j] == ‘.‘) y[i][j] = cnty;
75                 if(str[i][j] == ‘X‘) cnty ++;
76             }
77             cnty ++;
78         }
79         for(int i = 0; i < n; i ++) {
80             for(int j = 0; j < n; j ++) {
81                 if(str[i][j] == ‘.‘) g[x[i][j]][y[i][j]] = true;
82             }
83         }
84         printf("%d\n", hungary());
85     }
86     return 0;
87 }