好莱坞最负盛名的机灵老鼠与笨猫的故事——汤姆和杰利，又开始另一回合的笑料趣闻。这对活宝不仅为人类提供了五十年的欢乐趣事，夺得七座金项奖，不仅打破多项记录，他们还打破盘子、台灯、破坏邻居等……
杰利与尿布小灰鼠塔菲同住在这个人家的老鼠洞里，看起来像是被汤姆监视着，但杰利却非常机灵，总能使汤姆狡诈的诡计适得其反，总能让它自食其果。它们之间的关系常在一瞬间发生变化——化敌为友或势不两立：为敌时绞尽脑汁，互不相让；为友时，亲如兄弟，谁也不记仇。
但是这一回，笨猫实在受不了小老鼠的折腾，打算好好地休息休息，但是小老鼠可不会那么容易放过它。为了防止小老鼠去捣乱，他打算去把老鼠的洞口堵起来，但是，他不知道怎么去堵会比较好，所以他想让你帮帮他。
杰利的洞口可以用一个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
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和搜索来做，待补充！！！！！！