问题
该题看上去与二分图匹配无关，但其实可以转化成二分图匹配。一个骨牌恰好覆盖两格，而这两格必须是相邻的。因此如果把相邻的两格看成分别属于X、Y两个集合的节点，相邻的节点之间认为有一条（黑色）边相连，放骨牌看做将被覆盖的两格之间的边染成红色；由于一格（一个节点）只能被一个骨牌覆盖（被一条红边连接），那么连接的方式整个就是二分图的一个匹配。如何构建这张图呢？由于相邻的点属于不同的集合，因此仿照国际象棋的棋盘“间隔地”染色就好了。于是，相邻格子之间对应的边连接的都是属于不同集合的节点，相同集合的节点因为对应的不是相邻格子都不直接相连，形成了二分图。最后，能放置骨牌的最大数量就是二分图最大匹配中的边数。
二分图最大匹配可以用匈牙利算法解决，也可以转化成最大流解决，本次使用前者。匈牙利算法的核心操作其实与后者还挺像，后者是寻找增流路径，而前者是寻找一个“交互道路”（节点颜色交替的道路），其实都可以理解为增广道路（augmentation path）。只不过，由于在二分图匹配中一条边要么就是选要么就是不选，相当于是特殊的“流”，0或者1，因此最大流的“退流”操作，被简化为了异或操作。无论是从算法中具体的寻找增广道路去想，还是在宏观上进行问题的转化，本质上，二分图最大匹配就是最大流的特殊情况。
实现
本题首先需要建图。建图中，格子的坐标(i, j)（一个数对）需要被转化成点的序号（一个值），这里可以采用二维数组的索引方式。相邻格子染成不同颜色，可以用(i + j)的奇偶性来判断。其它的就很简单了。
建图之后直接调用匈牙利算法是可以的。不过为了加快一点速度，可以提供一个初始匹配。下面的代码在建图过程中简单地“铺上了横向的多米诺骨牌”作为初始匹配。
匈牙利算法中，寻找交互道路的过程用DFS实现。说白了，这一步就是从X集合中未搜索过的点出发，走一条在X、Y之间反复横跳的道路，最后以属于Y集合中而没有被匹配的点作为终点停止。
最终实现的算法类Hungarian接受三个参数初始化，分别是二分图的邻接表表示（因为该算法中常用到邻点，因此邻接表比邻接矩阵省时），每个点属于哪个集合，以及初始匹配是什么。构造函数中已调用核心算法，可以直接构造后调用getAns获取最大匹配数。
class Hungarian
{
vector< vector<int> >& graph; // adjacency list
vector<bool>& type; // X: 0; Y: 1
vector<int>& match; // not matched: -1
int n;
int end;
int total;
void dfs(const int now, vector<bool>& visited, stack<int>& path)
{
if (type[now] == 1)
{
if (match[now] == -1)
end = now; // return;
else // if (match[now] != -1)
{
// now -> match[now]
path.emplace(match[now]);
dfs(match[now], visited, path);
if (end != -1)
return;
path.pop();
}
}
else // if (type[now] == 0)
{
for (auto& iter : graph[now])
{
// now -> iter in Y
if (visited[iter] == false)
{
visited[iter] = true;
path.emplace(iter);
dfs(iter, visited, path);
if (end != -1)
break;
path.pop();
visited[iter] = false;
}
}
// break here // return;
}
}
void work()
{
queue<int> not_searched;
for (int i = 0; i < n; i++)
{
if (type[i] == 0 && graph[i].size())
{
if (match[i] == -1)
not_searched.emplace(i);
else
total++;
}
}
while (not_searched.size())
{
int start = not_searched.front();
not_searched.pop();
vector<bool> visited(n, false);
stack<int> path;
end = -1;
path.emplace(start);
dfs(start, visited, path);
if (end != -1) // find an augmenting path
{ // start -> ... -> end
total++;
while (path.size())
{
int tmp = path.top();
path.pop();
match[tmp] = path.top();
match[path.top()] = tmp;
path.pop();
}
}
}
}
public:
Hungarian(vector< vector<int> >& _g, vector<bool>& _t, vector<int>& _m):
graph(_g), type(_t), match(_m), n(_g.size()), total(0)
{
work();
}
int getAns()
{
return total;
}
};
class Solution
{
int N;
int M;
int points;
bool in_graph(const int x, const int y)
{
return 0 <= x && x < N && 0 <= y && y < M;
}
int get_index(const int x, const int y)
{
return x * M + y;
}
bool get_type(const int x, const int y)
{
return (x + y) % 2;
}
public:
int domino(int n, int m, vector<vector<int>>& broken)
{
N = n;
M = m;
points = n * m;
bool _broken[8][8] = { 0 };
vector< vector<int> > graph(points); // adjacency list
vector<bool> type(points, 0); // X: 0; Y: 1
vector<int> match(points, -1); // not matched: -1
for (auto& iter : broken)
{
_broken[iter[0]][iter[1]] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (!_broken[i][j])
{
int now = get_index(i, j);
type[now] = get_type(i, j);
if (in_graph(i - 1, j) && !_broken[i - 1][j])
{ // up
graph[now].push_back(get_index(i - 1, j));
}
if (in_graph(i + 1, j) && !_broken[i + 1][j])
{ // down
graph[now].push_back(get_index(i + 1, j));
}
if (in_graph(i, j - 1) && !_broken[i][j - 1])
{ // left
graph[now].push_back(get_index(i, j - 1));
}
if (in_graph(i, j + 1) && !_broken[i][j + 1])
{ // right
int right = get_index(i, j + 1);
graph[now].push_back(right);
if (type[now] == 0)
{
match[now] = right;
match[right] = now;
}
}
}
}
} // for in i
return Hungarian(graph, type, match).getAns();
}
};