[cpp]
/*
題意：N*M的矩形，向其中填充1*2的小塊矩形，黑色的部分不能填充，問最多可以填充多少塊。
題解：黑白棋最大匹配
將棋盤中i+j為奇數的做A集合，偶數的做B集合，相鄰的則建立聯系。於是便轉換成尋找最大匹配的問題
*/
#include <iostream>
#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)
{
int u = G[t][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
