HDU-1045 Fire Net【缩点二分图匹配（匈牙利算法）】

题目链接
题意：
给出一个矩阵，由.和X组成代表空地和墙，往空地尽量多的放英雄，每两个英雄的位置满足：1.不在同一行同一列。2.在同一行或同一列但是有墙隔开
思路：
将每一行连起来的部分缩成一个点，因为这一部分不可能放置两个英雄，这一个集合作为X部，将列做同样的处理，这一集合作为Y部，将X和Y中有交点的两个元素（即在图中有重叠部分）连边，这样的只能放一个，最后统计一下就可

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 125
using namespace std;

int n, cntx, cnty, cx[MAXN], cy[MAXN], tmp[15][15];
char map[6][6];
bool vis[MAXN << 1], flag[MAXN][MAXN];

void build() {
    memset(flag, 0, sizeof flag);
    memset(tmp, 0, sizeof tmp);
    cntx = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            if (map[i][j] == 'X')++cntx;
            else tmp[i][j] = cntx;
        if (map[i][n - 1] != 'X')++cntx;
    }

    cnty = 1;
    for (int j = 0; j < n; ++j) {
        for (int i = 0; i < n; ++i)
            if (map[i][j] == 'X')++cnty;
            else flag[tmp[i][j]][cnty] = 1;
        if (map[n - 1][j] != 'X')++cnty;
    }

}

bool dfs(int u) {
    for (int v = 1; v <= cnty; ++v)
        if (!vis[v] && flag[u][v]) {
            vis[v] = 1;
            if (!cy[v] || dfs(cy[v])) {
                cx[u] = v, cy[v] = u;
                return 1;
            }
        }
    return 0;
}
int main() {
    while (~scanf("%d", &n) && n) {
        for (int i = 0; i < n; ++i)
            scanf("%s", map[i]);
        build();
        memset(cx, 0, sizeof cx);
        memset(cy, 0, sizeof cy);
        int ans = 0;
        for (int i = 1; i <= cntx; ++i)
            if (!cx[i]) {
                memset(vis, 0, sizeof(vis));
                ans += dfs(i);
            }
        //for(int i=1;i<cntx;i++) cout<<cx[i]<<' ';cout<<endl;
        //for(int i=1;i<cnty;i++) cout<<cy[i]<<' ';cout<<endl;
        printf("%d\n", ans);
    }
    return 0;
}