随笔档案

#include <cstdio>
#include <cstring>
using namespace std;
int g[33][33],linky[33];
bool vis[33];
char map[5][5];
int mapl[5][5],mapr[5][5];
int n , m;
bool find(int u) {
    for(int v=1;v<=m;v++)
        if(g[u][v] && !vis[v]) {
            vis[v] = 1;
            if(linky[v]==-1 || find(linky[v])) {
                linky[v] = u;
                return true;   
            }   
        }
    return false;
}
int hungry() {
    int ret = 0;
    memset(linky,-1,sizeof(linky));
    for(int u=1;u<=n;u++) {
        memset(vis,0,sizeof(vis));
        if(find(u)) ret ++;  
    }   
    return ret;
}
int main() {
    int N;
    while(~scanf("%d",&N) && N) {
        memset(mapl,0,sizeof(map));
        memset(mapr,0,sizeof(mapr));
        for(int i=0;i<N;i++) scanf("%s",map[i]);
        n = m = 0;
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(map[i][j] == 'X') mapl[i][j] = mapr[i][j] = -1;
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) {
            while(mapr[i][j]==-1&&j<N) j++;
            n ++;
            while(mapr[i][j]!=-1&&j<N) mapr[i][j++] = n;   
        }
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) {
            while(mapl[j][i]==-1&&j<N) j++;
            m ++;
            while(mapl[j][i]!=-1&&j<N) mapl[j++][i] = m;   
        }
        memset(g,0,sizeof(g));
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++) {
            if(mapr[i][j]!=-1&&mapl[i][j]!=-1) g[mapr[i][j]][mapl[i][j]] = 1;   
        }
        int ans = hungry();
        printf("%d\n",ans);
    }
    return 0;   
}