/*
题意：N*M的矩形，向其中填充1*2的小块矩形，黑色的部分不能填充，问最多可以填充多少块。
?
题解：黑白棋最大匹配
将棋盘中i+j为奇数的做A集合，偶数的做B集合，相邻的则建立联系。于是便转换成寻找最大匹配的问题
*/?
?
#include
#define re(i, n) for(int i = 0; i < n; ++ i)?
using namespace std;?
?
const int nMax = 105;?
const int mMax = 10010;?
int N, M, K;?
int map[nMax][nMax];//存储图中的数据?
int G[mMax][5];//G[k][]表示与k = i * M + j相连的可填充点，邻接表建立AB集合之间的联系?
int link[mMax];?
int useif[mMax];?
int num;//最大匹配数?
int V;// N * M ：总节点数?
?
void buildGraph()//建图，对G进行处理?
{?
??? memset(G, -1, sizeof(G));?
??? re(i, N) re(j, M)?
??? {?
??????? int u = i * M + j;?
??????? int v = 0;?
??????? if(!map[i][j] && ((i + j) & 1) == 1)//此点可填充，并且i+j为奇数?
??????? {?
??????????? //左?
??????????? if(j > 0 && !map[i][j - 1])?
??????????? {?
??????????????? G[u][v ++] = u - 1;?
??????????? }?
??????????? //右?
??????????? if(j < M - 1 && !map[i][j + 1])?
??????????? {?
??????????????? G[u][v ++] = u + 1;?
??????????? }?
??????????? //上?
??????????? if(i > 0 && !map[i - 1][j])?
??????????? {?
??????????????? G[u][v ++] = u - M;?
??????????? }?
??????????? //下?
??????????? if(i < N - 1 && !map[i + 1][j])?
??????????? {?
??????????????? G[u][v ++] = u + M;?
??????????? }?
??????? }?
??? }?
}?
?
int dfs(int t)?
{?
??? for(int i = 0; G[t][i] != -1; ++ i)?
??? {?
??????? if(!useif[u])//因为邻接表结构，所以t、u肯定有联系，无需在进行map[][]判断?
??????? {?
??????????? useif[u] = 1;? www.2cto.com
??????????? if(link[u] == -1 || dfs(link[u]))?
??????????? {?
??????????????? link[u] = t;?
??????????????? return 1;?
??????????? }?
??????? }?
??? }?
??? return 0;?
}?
?
int maxMatch()?
{?
??? num = 0;?
??? memset(link, -1, sizeof(link));?
??? re(i, V)?
??? {?
??????? memset(useif, 0, sizeof(useif));?
??????? if(dfs(i))?
??????????? num ++;?
??? }?
??? return num;?
}?
?
int main()?
{?
??? //freopen("f://data.in", "r", stdin);?
??? while(scanf("%d %d", &N, &M) != EOF)?
??? {?
??????? if(!N && !M) break;?
??????? scanf("%d", &K);?
??????? memset(map, 0, sizeof(map));?
??????? re(i, K)??
??????? {?
??????????? int a, b;?
??????????? scanf("%d %d", &a, &b);?
??????????? map[a - 1][b - 1] = 1;?
??????? }?
??????? V = N * M;?
??????? buildGraph();?
??????? maxMatch();?
??????? printf("%d\n", num);?
??????? re(i, V)?
??????? {?
??????????? if(link[i] != -1)//因为最大匹配，所以不会有重复，查找一次，然后输出即可?
??????????? {?
??????????????? int u = link[i];?
??????????????? printf("(%d,%d)--(%d,%d)\n", u / M + 1, u % M + 1, i / M + 1, i % M + 1);?
??????????? }?
??????? }?
??????? printf("\n");?
??? }?
??? return 0;?
}?
作者：lhshaoren