又是二分图 boj1298 格子覆盖问题

Dear Jerry,I'm TomSubmit: 373   Accepted:106Time Limit: 5000MS  Memory Limit: 65535KDescription
好莱坞最负盛名的机灵老鼠与笨猫的故事——汤姆和杰利，又开始另一回合的笑料趣闻。这对活宝不仅为人类提供了五十年的欢乐趣事，夺得七座金项奖，不仅打破多项记录，他们还打破盘子、台灯、破坏邻居等……
杰利与尿布小灰鼠塔菲同住在这个人家的老鼠洞里，看起来像是被汤姆监视着，但杰利却非常机灵，总能使汤姆狡诈的诡计适得其反，总能让它自食其果。它们之间的关系常在一瞬间发生变化——化敌为友或势不两立：为敌时绞尽脑汁，互不相让；为友时，亲如兄弟，谁也不记仇。
但是这一回，笨猫实在受不了小老鼠的折腾，打算好好地休息休息，但是小老鼠可不会那么容易放过它。为了防止小老鼠去捣乱，他打算去把老鼠的洞口堵起来，但是，他不知道怎么去堵会比较好，所以他想让你帮帮他。
杰利的洞口可以用一个R*C的矩阵描述,R行C列,#表示的是墙壁,而*表示空洞,汤姆可以用1*2的方砖去填补它,只要有方法把空洞全部填满,那么就可以挡住杰利,不然的话杰利就总能想到办法跑出来,以下就是一个成功的填补方案。


Input
第i组数据输出前，请先输出“Case I:”.
多组测试数据。
每一组数据第一行为R和C,(R,C<=8)。
以下R行,每行C个字符,表示洞口的描述.


Output
如果有一种方案可以把洞口完全填上,请输出”yes”,否则输出”no”.


Sample Input

5 5
#####
#*#**
#***#
#****
#*##*
5 5
#####
#*#**
#***#
#****
#*#**
5 5
#####
#*#**
###*#
#*#**
####*


Sample Output

Case 1:
yes
Case 2:
no
Case 3:
no

解题思路：

1.二分图：
将所有需要填充的点作为二分图的节点，两点之间有边表示这两个点相邻。那么要求的结果就等价于求最小点集覆盖，这些点是所有存在的边的其中一个顶点，并且要保证一条边的两个点不能同时被选中！！！！
只要最后选出来的边的数量等于需要覆盖的格子的数量，说明可以成功覆盖，否则不行。

代码如下：
#include 
#include 
using namespace std;

char map[10][10];
bool path[100][100], chk[100];
int node, xm[100], ym[100], nb[100][100];

/* 构建需要填充的格子之间的相邻关系 */
int init_path(int row, int col)
{
    int i, j, k = 0;
    for (i=0 ; i    {
        for (j=0 ; j        {
            if ('#' == map[i][j])
                continue;
            nb[i][j] = k++; /* 计算需要覆盖的格子数，后面还需用它来作结果判定 */
        }
    }
    int cur_nb;
    for (i=0 ; i    {
        for (j=0 ; j        {
            if (-1 == nb[i][j])
                continue;
            cur_nb = nb[i][j];
            if (i - 1 >= 0 && -1 != nb[i - 1][j])
                path[cur_nb][nb[i - 1][j]] = true;
            if (j - 1 >= 0 && -1 != nb[i][j - 1])
                path[cur_nb][nb[i][j - 1]] = true;
            if (i + 1 < row && -1 != nb[i + 1][j])
                path[cur_nb][nb[i + 1][j]] = true;
            if (j + 1 < col && -1 != nb[i][j + 1])
                path[cur_nb][nb[i][j + 1]] = true;
        }
    }
    return k;
}

bool search_path(int u)
{
    int v;
    for (v=0 ; v    {
        if (path[u][v] && !chk[v])
        {
            chk[v] = true;
            /*
             * ym[v]=-1 表示该右边节点没有对应的边，可以选择这个点
             * 否则，说明这个右边点已被选择过，则递归这个右边节点对应的左边节点l，从l查找一个可用边，然后进行取反操作
             * */
            if (-1 == ym[v] || search_path(ym[v]))
            {
                /* reverse max flow */
                ym[v] = u;
                xm[u] = v;
                return true; /* 只要找到一条增广路径，该函数就退出，不在查找其他点 */
            }
        }
    }
    return false;
}

int max_match()
{
    int u, ret;
    memset(xm, -1, sizeof(xm));
    memset(ym, -1, sizeof(ym));
    ret = 0;
    for (u=0 ; u    {
        memset(chk, false, sizeof(chk));
        if (search_path(u))
            ret++;
    }
    return ret;
}

int main(int argc, char *argv[])
{
    int R, C, i, j = 1, max_flow;
    while (EOF != scanf(" %d %d ", &R, &C))
    {
        memset(path, false, sizeof(path));
        memset(nb, -1, sizeof(nb));
        for (i=0 ; i            gets(map[i]);
        node = init_path(R, C);
        max_flow = max_match();
        
        cout << "Case " << j++ << ":" << endl;
        if (node == max_flow)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
}


该题还可以用dp和搜索来做，待补充！！！！！！