欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode LCP 4. 覆盖

程序员文章站 2022-04-16 12:54:17
...

你有一块棋盘,棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌,你想把这些骨牌不重叠地覆盖在完好的格子上,请找出你最多能在棋盘上放多少块骨牌?这些骨牌可以横着或者竖着放。

输入:n, m代表棋盘的大小;broken是一个b * 2的二维数组,其中每个元素代表棋盘上每一个坏掉的格子的位置。

输出:一个整数,代表最多能在棋盘上放的骨牌数。

示例 1:

输入:n = 2, m = 3, broken = [[1, 0], [1, 1]]
输出:2
解释:我们最多可以放两块骨牌:[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。(见下图)
leetcode LCP 4. 覆盖

示例 2:

输入:n = 3, m = 3, broken = []
输出:4
解释:下图是其中一种可行的摆放方式

leetcode LCP 4. 覆盖

限制:

1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m

来源:力扣(LeetCode)
题目链接:https://leetcode-cn.com/problems/broken-board-dominoes
题目著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路分析

每次两块,那么很明显时匹配型问题,那么二分匹配采用匈牙利算法解决即可。
将每一个方格标记坐标号,分为偶数与奇数,那么即可用偶数点去匹配奇数点即可。
特别注意的是错误方块的标记,其他没什么了。


代码解析
class Solution {
	int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };//方向
	vector<int> two_point_relationship, visited;//匹配关系,访问标记
	vector<vector<int> > point, edge;
	int find(int pre) {
		for (auto& it : point[1]) {//奇数点
			if (edge[pre][it] && !visited[it]) {//未被访问并且有连接关系
				visited[it] = 1;//访问标记
				if (two_point_relationship[it] == 0 || find(two_point_relationship[it])){//存在匹配点
                    two_point_relationship[it] = pre;
                    return 1;
                }
			}
		}
		return 0;
	}
public:
	int domino(int n, int m, vector<vector<int> >& broken) {
		vector<vector<int> > bre_map(n, vector<int>(m, 0));//row:n,col:m,value:0
		int answer = 0;//返回值
		edge.resize(m * n  + 1, vector<int>(m * n + 1));//大小扩展
		point.resize(2);
		for (auto it : broken)
			bre_map[it[0]][it[1]] = 1;//破坏点
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (bre_map[i][j] == 1) continue;
				int id = i * m + j + 1;//编号
				if ((i + j) % 2 == 0)
					point[0].push_back(id);//偶数编号点
				else
					point[1].push_back(id);//奇数编号点
				for (int k = 0; k < 4; ++k) {//四个方向判断连线
					int nx = dx[k] + i, ny = dy[k] + j;
					int temp_id = nx * m + ny + 1;//id计算
					if (nx >= 0 && ny >= 0 && nx < n && ny < m && bre_map[nx][ny] == 0)
						edge[id][temp_id] = edge[temp_id][id] = true;//连接
				}
			}
		}
		two_point_relationship = vector<int>(m * n + 1, 0);//初始化
		for (auto &it:point[0]) {//偶数点
			visited.assign(m * n + 1, false);//重置0
			answer += find(it);
		}
		return answer;
	}
};

leetcode LCP 4. 覆盖