1 #include <climits>  2 #include <cstdio>  3 #include <cstring>  4 #include <cctype>  5 #include <cmath>  6 #include <ctime>  7 #include <cstdlib>  8 #include <cstdarg>  9 #include <iostream> 10 #include <fstream> 11 #include <iomanip> 12 #include <sstream> 13 #include <exception> 14 #include <stdexcept> 15 #include <memory> 16 #include <locale> 17 #include <bitset> 18 #include <deque> 19 #include <list> 20 #include <map> 21 #include <set> 22 #include <queue> 23 #include <stack> 24 #include <vector> 25 #include <algorithm> 26 #include <iterator> 27 #include <functional> 28 #include <string> 29 #include <complex> 30 #include <valarray> 31  32 using namespace std; 33  34 const int maxn=110; 35 int N; 36 char G[maxn][maxn]; 37 int row[maxn][maxn]; 38 int col[maxn][maxn]; 39 int V; 40 vector<int> Gra[maxn*maxn]; 41 int match[maxn*maxn]; 42 bool used[maxn*maxn]; 43  44 void add_edge(int u,int v){ 45     Gra[u].push_back(v); 46     Gra[v].push_back(u); 47 } 48  49 bool dfs(int v) 50 { 51     used[v]=true; 52     for(int i=0; i<Gra[v].size(); i++) { 53         int u=Gra[v][i]; 54         int w=match[u]; 55         if (w<0||(!used[w]&&dfs(w))) { 56             match[v]=u; 57             match[u]=v; 58             return true; 59         } 60     } 61     return false; 62 } 63  64 void b_match() 65 { 66     int res=0; 67     memset(match, -1, sizeof(match)); 68     for (int v=0; v<V; v++) { 69         if (match[v]<0) { 70             memset(used, 0, sizeof(used)); 71             if (dfs(v)) { 72                 res++; 73             } 74         } 75     } 76     printf("%d\n",res); 77 } 78  79 void build2() { 80     int row_cnt = 0; 81     int col_cnt = 0; 82  83     for (int i = 0; i < N; i++) 84         for (int j = 0; j < N; j++) 85             row[i][j] = col[i][j] = 0; 86  87     for (int i = 0; i < N; i++) { 88         row_cnt++; 89         for (int j = 0; j < N; j++) { 90             if (‘X‘==G[i][j]) { 91                 bool flag =  j==0; 92                 while (j+1<N && ‘X‘==G[i][j+1]) j++; 93                 if (j+1==N) flag = true; 94 //                if (!flag) 95                     row_cnt++; 96             } else row[i][j] = row_cnt; 97         } 98     } 99     for (int j = 0; j < N; j++) {100         col_cnt++;101         for (int i = 0; i < N; i++) {102             if (‘X‘==G[i][j]) {103                 bool flag = i==0;104                 while (i+1<N && ‘X‘==G[i+1][j]) i++;105                 if (i+i==N) flag = true;106 //                if (!flag)107                     col_cnt++;108             } else col[i][j] = col_cnt;109         }110     }111     V=row_cnt+1;112 //printf("V: %d\n",V);113     for (int i = 0; i <= V; i++) Gra[i].clear();114 115     for(int i=0;i<N;i++)116     {117         for(int j=0;j<N;j++)118         {119             if(G[i][j]==‘.‘) {120                 add_edge(row[i][j],row_cnt+col[i][j]);121 //printf("row %d col %d\n",row[i][j],col[i][j]);122             }123         }124     }125 //for(int i=0;i<V;i++)126 //{127 //    printf("%d (%d): ", i, Gra[i].size());128 //    for(int j=0;j<Gra[i].size();j++)129 //    {130 //        printf("%d ",Gra[i][j]);131 //    }132 //    puts("");133 //}134 //    for (int i = 0; i < N; i++) {135 //        for (int j = 0; j < N; j++)136 //            printf("%d ", row[i][j]);137 //        puts("");138 //    }139 //    puts("---------------------");140 //        for (int i = 0; i < N; i++) {141 //        for (int j = 0; j < N; j++)142 //            printf("%d ", col[i][j]);143 //        puts("");144 //    }145 146 }147 148 int main()149 {150 #ifdef PIT151     freopen("A.in", "r", stdin);152 #endif // PIT153     while(scanf("%d",&N)!=EOF)154     {155         int cntdian=0;156         for(int i=0;i<N;i++)157         {158             scanf("%s",G[i]);159 for(int j=0;j<N;j++)160 {161     if(G[i][j]==‘.‘) cntdian++;162 }163 //printf("%d\n",cntdian);164 //            Gra[i].clear();165         }166         build2();167         //build_graph();168         b_match();169     }170     return 0;171 }