二分图匹配

水题

如果没有墙，我们直接放碉堡的话。
我们可以肯定在所有放置的坐标中同一个行不能出现两次，同一个列不能出现两次。

那么，有了墙的话意味着什么呢？
意味着，我们有了额外的行和列！！！
我们只要重新规定行和列就可以了。

即，我们要找每个新出的区域。

代码如下：

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
char g[5][5];
int ghx[5][5];
int ghy[5][5];
int n;
struct edge{
    int to, next;
}E[100];
int head[50];
int cnt = 1;
void add(int from, int to) {
    E[cnt].to = to;E[cnt].next = head[from];
    head[from] = cnt++;
}
int rightTo[20], leftTo[20];
bool vis[50];
int matchpath(int u) {
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (vis[v])continue;vis[v] = true;
        if (rightTo[v] == -1 || matchpath(rightTo[v])) {
            leftTo[u] = v;
            rightTo[v] = u;
            return true;
        }
    }return false;
}
int Hungulian(int left_tot,int right_tot) {
    fill(rightTo, rightTo + right_tot + 1, -1);
    fill(leftTo, leftTo + left_tot + 1, -1);
    int ans = 0;
    for (int i = 1;i <= left_tot;++i) {
        fill(vis, vis + right_tot + 1, false);
        if (leftTo[i] == -1 && matchpath(i))
            ++ans;
    }return ans;
}


int main() {
    while (scanf("%d", &n)) {
        if (n == 0) break;
        fill(head, head + 50, 0);cnt = 1;
        for (int i = 1;i <= n;++i)
        scanf("%s", &g[i][1]);
        int right_tot = 0;
        int left_tot = 0;
        bool he = false;
        for (int i = 1;i <= n;++i) {
            for (int j = 1;j <= n;++j) {
                if (g[i][j] == 'X') {
                    if (!he) {
                        ++left_tot;
                        he = true;
                    }
                }
                else if (j == 1 && !he)++left_tot;
                if (g[i][j] != 'X') {
                    ghx[i][j] = left_tot;
                    he = false;
                }
            }
        }
        he = false;
        for (int i = 1;i <= n;++i) {
            for (int j = 1;j <= n;++j) {
                if (g[j][i] == 'X') {
                    if (!he) {
                        ++right_tot;
                        he = true;
                    }
                }
                else if (j == 1 && !he)++right_tot;
                if (g[j][i] != 'X') {
                    ghy[j][i] = right_tot;
                    he = false;
                }
            }
        }for (int i = 1;i <= n;++i)
            for (int j = 1;j <= n;++j)
                if (g[i][j] != 'X')
                    add(ghx[i][j], ghy[i][j]);
        printf("%d\n", Hungulian(left_tot, right_tot));
    }
}