【分类讨论】【割点】1568. 使陆地分离的最少天数

作者推荐

动态规划的时间复杂度优化

本文涉及知识点

分类讨论
割点原理及封装好的割点类(预计2024年3月11号左右发布）

LeetCode1568. 使陆地分离的最少天数

给你一个大小为 m x n ，由若干 0 和 1 组成的二维网格 grid ，其中 1 表示陆地， 0 表示水。岛屿 由水平方向或竖直方向上相邻的 1 （陆地）连接形成。
如果 恰好只有一座岛屿 ，则认为陆地是 连通的 ；否则，陆地就是 分离的 。
一天内，可以将 任何单个 陆地单元（1）更改为水单元（0）。
返回使陆地分离的最少天数。
示例 1：
输入：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
在这里插入图片描述

输出：2
解释：至少需要 2 天才能得到分离的陆地。
将陆地 grid[1][1] 和 grid[0][2] 更改为水，得到两个分离的岛屿。
示例 2：
在这里插入图片描述

输入：grid = [[1,1]]
输出：2
解释：如果网格中都是水，也认为是分离的 ([[1,1]] -> [[0,0]])，0 岛屿。
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] 为 0 或 1

分类讨论

岛屿数只要不为1都是分离的陆地。
岛屿数 = 连通区域 - 水单元数。
一个岛屿只有一块陆地或两块陆地，无法分割，只能花一天或两天变成0岛屿。
3块陆地的岛屿只需要一天就可以分割。由于是4连接，无法两两相连。
4块陆地的岛屿一定可以两天分离，右上的那块陆地 右边和上边没有连接，最坏的情况把左下的两块陆地消掉，右上的陆地和余下的陆地就成了两个岛屿。

如何查看岛屿数量是否为1

并集查找后，看各陆地的是否是同一连通区域。

如果计算能否一天搞定

枚举各陆地，删除后看能否符合题意。

大致思路

一，岛屿数量是否为1，如果不是返回0.
二，枚举各陆地，删除，如果岛屿数量不为1，返回1。
三，返回2。

割点

一，岛屿数量是否为1，如果不是返回0.
二，如果只有1块或2块陆地，直接陆地数量。
三，如果存在割点，返回1。
四，返回2。

代码

核心代码

class CEnumGridEdge
{
public:
	void Init()
	{
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
	}
	const int m_r, m_c;
protected:
	CEnumGridEdge(int r, int c) :m_r(r), m_c(c)
	{

	}
	void Move(int preR, int preC, int r, int c)
	{
		if ((r < 0) || (r >= m_r))
		{
			return;
		}
		if ((c < 0) || (c >= m_c))

		{
			return;
		}
		OnEnumEdge(preR, preC, r, c);
	};
	virtual void OnEnumEdge(int preR, int preC, int r, int c) = 0;
};
//割点
class CCutPoint
{
public:
	CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
	{
		m_vTime.assign(m_iSize, -1);
		m_vVisitMin.assign(m_iSize, -1);
		for (int i = 0; i < m_iSize; i++)
		{
			if (-1 != m_vTime[i])
			{
				continue;
			}
			m_iRegionCount++;
			dfs(i, -1, vNeiB);
		}
	}
	int RegionCount()const
	{
		return m_iRegionCount;
	}
	vector<int> CutPoints()const
	{
		return m_vCutPoints;
	}
protected:
	void dfs(int cur, int parent, const vector<vector<int>>& vNeiB)
	{
		auto& curTime = m_vTime[cur];
		auto& visitMin = m_vVisitMin[cur];
		curTime = m_iTime++;
		visitMin = curTime;
		int iMax = -1;
		int iChildNum = 0;
		for (const auto& next : vNeiB[cur])
		{
			if (next == parent)
			{
				continue;
			}
			if (-1 != m_vTime[next])
			{
				visitMin = min(visitMin, m_vTime[next]);
				continue;
			}
			iChildNum++;
			dfs(next, cur, vNeiB);
			visitMin = min(visitMin, m_vVisitMin[next]);
			iMax = max(iMax, m_vVisitMin[next]);
		}
		if (-1 == parent)
		{
			if (iChildNum >= 2)
			{
				m_vCutPoints.emplace_back(cur);
			}
		}
		else
		{
			if (iMax >= curTime)
			{
				m_vCutPoints.emplace_back(cur);
			}
		}
	}
	vector<int> m_vTime;//各节点到达时间，从0开始。 -1表示未处理
	vector<int> m_vVisitMin;// 
	int m_iTime = 0;
	int m_iRegionCount = 0;
	vector<int> m_vCutPoints;
	const int m_iSize;
};


class CNeiBo : public CEnumGridEdge
{
public:
	CNeiBo(const vector<vector<int>>& grid, int r, int c):CEnumGridEdge(r,c), m_iMaskCount(r*c), m_grid(grid)
	{
		m_vNeiBo.resize(m_iMaskCount);
		Init();
	}
	// 通过 CEnumGridEdge 继承
	virtual void OnEnumEdge(int preR, int preC, int r, int c) override
	{
		if (m_grid[preR][preC] && m_grid[r][c])
		{
			const int iMask = m_c * r + c;
			const int iPre = m_c * preR + preC;
			m_vNeiBo[iPre].emplace_back(iMask);
		}
	}
	const int m_iMaskCount;
	vector<vector<int>> m_vNeiBo;
	const vector<vector<int>>& m_grid;
};
class Solution {
public:
	int minDays(vector<vector<int>>& grid) {
		CNeiBo neiBo(grid, grid.size(), grid[0].size());
		CCutPoint cut(neiBo.m_vNeiBo);
		int iZeroCount = 0;
		for (const auto& v : grid)
		{
			iZeroCount += std::count(v.begin(), v.end(), 0);
		}
		if (1 != cut.RegionCount()- iZeroCount)
		{
			return 0;
		}
		if (neiBo.m_iMaskCount - iZeroCount <= 2)
		{
			return neiBo.m_iMaskCount - iZeroCount;
		}
		if (cut.CutPoints().size())
		{
			return 1;
		}
		return 2;
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159

测试用例


template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<vector<int>> grid;
	{
		Solution sln;
		grid = { {0,1,1,0},{0,1,1,0},{0,0,0,0} };
		auto res = sln.minDays(grid);
		Assert(2, res);
	}
	
	

	{
		Solution sln;
		grid = { {0},{0} };
		auto res = sln.minDays(grid);
		Assert(0, res);
	}

	{
		Solution sln;
		grid = { {1},{1} ,{1} };
		auto res = sln.minDays(grid);
		Assert(1, res);
	}
		
	{
		Solution sln;
		grid = { {1},{1} };
		auto res = sln.minDays(grid);
		Assert(2, res);
	}
	{
		Solution sln;
		grid = { {1} };
		auto res = sln.minDays(grid);
		Assert(1, res);
	}

	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

2024年3月9

使用新的割点封装类。

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		return vNeiBo;
	}
};

//割点
class CCutPoint
{
public:
	CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
	{
		m_vNodeToTime.assign(m_iSize, -1);
		m_vCutNewRegion.resize(m_iSize);
		for (int i = 0; i < m_iSize; i++)
		{
			if (-1 == m_vNodeToTime[i])
			{
				m_vRegionFirstTime.emplace_back(m_iTime);
				dfs(vNeiB, i, -1);
			}
		}	
	}
	int dfs(const vector<vector<int>>& vNeiB,const int cur, const int parent)
	{
		int iMinTime = m_vNodeToTime[cur] = m_iTime++;
		int iRegionCount = (-1 != parent);
		for (const auto& next : vNeiB[cur])		{
			if (-1  != m_vNodeToTime[next])			{
				iMinTime = min(iMinTime, m_vNodeToTime[next]);
				continue;
			}
			const int childMinTime = dfs(vNeiB, next, cur);
			iMinTime = min(iMinTime, childMinTime);
			if (childMinTime >= m_vNodeToTime[cur])			{
				iRegionCount++;
				m_vCutNewRegion[cur].emplace_back(m_vNodeToTime[next], m_iTime);
			}
		}
		if (iRegionCount < 2)
		{
			m_vCutNewRegion[cur].clear();
		}
		return iMinTime;
	}
	const int m_iSize;
	const vector<int>& Time()const { return m_vNodeToTime; }//各节点的时间戳
	const vector<int>& RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳
	vector<bool> Cut()const { 
		vector<bool> ret;
		for (int i = 0; i < m_iSize; i++)
		{
			ret.emplace_back(m_vCutNewRegion[i].size());
		}
		return ret; }//是否是割点
protected:
	vector<int> m_vNodeToTime;
	vector<int> m_vRegionFirstTime;
	vector < vector<pair<int, int>>> m_vCutNewRegion; //m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后，时间戳[left,r)的节点会形成新区域
	int m_iTime = 0;
};

class Solution {
public:
	int minDays(vector<vector<int>>& grid) {
		auto pr = [&](int r, int c) {return grid[r][c] == 1; };
		auto neiBo = CNeiBo::Grid(grid.size(), grid[0].size(), pr, pr);
		CCutPoint cut(neiBo);
		int iZeroCount = 0;
		for (const auto& v : grid)
		{
			iZeroCount += std::count(v.begin(), v.end(), 0);
		}
		if (1 != cut.RegionFirstTime().size() - iZeroCount)
		{
			return 0;
		}
		if (neiBo.size() - iZeroCount <= 2)
		{
			return neiBo.size() - iZeroCount;
		}
		auto vCut = cut.Cut();
		const int iCutCount = std::count(vCut.begin(), vCut.end(), true);
		if (iCutCount)
		{
			return 1;
		}
		return 2;
	}
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147

2023年4月版

class Solution {
public:
int minDays(vector& grid) {
m_r = grid.size();
m_c = grid[0].size();
int iTotal = 0;
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
if (1 == grid[r][c])
{
iTotal++;
}
}
}
if (iTotal < 2)
{
return iTotal;
}
if (iTotal != AnyAUnionNum(grid))
{
return 0;
}
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
if (0 == grid[r][c])
{
continue;
}
grid[r][c] = 0;
if (iTotal != 1+AnyAUnionNum(grid))
{
return 1;
}
grid[r][c] = 1;
}
}
return 2;
}
int AnyAUnionNum(const vector& grid)
{
int iNum = 0;
for (int r = 0; r < m_r;r++ )
{
for (int c = 0; c < m_c; c++ )
{
if (1 == grid[r][c])
{
return NeiBNum(r, c, grid);
}
}
}
return 0;
}
int NeiBNum(int iR, int iC, const vector& grid)
{
std::unordered_set setRC;
queue> que;
setRC.emplace(iR*100+iC);
que.emplace(iR, iC);
while (que.size())
{
const auto it = que.front();
que.pop();
auto Add = [&](int r,int c)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (1 != grid[r][c])
{
return;
}
int iRCMask = 100 * r + c;
if (setRC.count(iRCMask))
{
return;
}
setRC.emplace(iRCMask);
que.emplace(r, c);
};
Add(it.first + 1, it.second);
Add(it.first - 1, it.second);
Add(it.first, it.second + 1);
Add(it.first, it.second - 1);
}
return setRC.size();
}
int m_r, m_c;
vector m_vNeiNum;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览59023 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/136162106"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！