洛谷：P2825 [HEOI2016/TJOI2016]游戏

题目链接：

解题思路： 我们先思考没有硬石头的话该怎么做： 若没有硬石头的话，则是一个很经典的二分图问题，即对于除了软石头之外的点，枚举每行，每列然后将像同行以及相同列连一条边做二分图的最大匹配即可： 然后我们来考虑这题：即有硬石头的情况： 我们可以把硬石头所在的行或列通过硬石头为分界点单独分为几个区域： 例如xx*x#**x即把一行分为了xx*x以及**x两个部分，然后按照没有硬石头的方式连边即可：

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 55, M = N * N * N;

int sum;
int n, m;
bool st[M];
int match[M];
int row[N][N];
int col[N][N];
char map[N][N];
int h[N * N], e[M], ne[M], idx;

void add(int a, int b)//邻接表模板
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}

bool find(int a)//二分图模板
{
    for (int i = h[a]; i != - 1; i = ne[i])
    {
        int b = e[i];
        if (st[b]) continue;
        st[b] = true;
        
        if (match[b] == -1 || find(match[b]))
        {
            match[b] = a;
            return true;
        }
    }
    
    return false;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    memset(match, -1, sizeof match);
    
    for (int i = 1; i <= n; i ++ ) cin >> map[i] + 1;
    
    for (int i = 1; i <= n; i ++ )//枚举行，判断所有行可以分为几个单独的行
        for (int j = 1; j <= m; j ++ )
        {
            if (map[i][j] == #) continue;
            if (j == 1 || map[i][j - 1] == #) sum ++ ;
            if (map[i][j] == x) continue;//注意这句话一定要写在前两句的后面因为每行的开头一定与上一行不同即sum++
            row[i][j] = sum;
        }
    
    for (int i = 1; i <= m; i ++ )//枚举列，同理
        for (int j = 1; j <= n; j ++ )
        {
            if (map[j][i] == #) continue;
            if (j == 1 || map[j - 1][i] == #) sum ++ ;
            if (map[j][i] == x) continue;
            col[j][i] = sum;
        }
    
    for (int i = 1; i <= n; i ++ ) //建图
        for (int j = 1; j <= m; j ++ )
                add(row[i][j], col[i][j]);
    
    int res = 0;
    for (int i = 1; i <= sum; i ++ )//枚举所有点
    {
        memset(st, false, sizeof st);
        if (find(i)) res ++ ;
    }
    
    cout << res << endl;
    
    return 0;
}