作者推薦
動態規劃的時間復雜度優化
本文涉及知識點
分類討論 割點
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;}
};
測試用例
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);}}
2023年4月版
class Solution {
public:
int minDays(vector<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<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<vector>& grid)
{
std::unordered_set setRC;
queue<pair<int, int>> 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<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++**實現。
)
