AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2024-04-10 55
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【分类讨论】【割点】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;
  }
};

测试用例

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);
  }
  
}

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;
  }
};

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++**实现。

文章标签：
算法
C++
测试技术
C#
闻缺陷则喜何志丹
目录
相关文章
闻缺陷则喜何志丹
|
7月前
|
算法 测试技术 C++
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目
闻缺陷则喜何志丹
49 1
闻缺陷则喜何志丹
|
7月前
|
算法 测试技术 C++
【状态压缩 容斥原理 组合数学】3116. 单面值组合的第 K 小金额
【状态压缩 容斥原理 组合数学】3116. 单面值组合的第 K 小金额
闻缺陷则喜何志丹
42 0
走在努力路上的自己
|
7月前
|
人工智能 算法
前缀和算法题（区间次方和、小蓝平衡和、大石头的搬运工、最大数组和）
前缀和算法题（区间次方和、小蓝平衡和、大石头的搬运工、最大数组和）
走在努力路上的自己
74 1
闻缺陷则喜何志丹
|
7月前
|
算法 测试技术 C#
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
闻缺陷则喜何志丹
50 0
LightOf
|
7月前
|
存储 算法 C++
第 284 场周赛（C++ | 枚举 | 分类讨论 | 最短路 | 建反图）
【4月更文挑战第1天】- [LeetCode 6031](https://leetcode-cn.com/problems/find-all-k-distant-indices-in-an-array/)：给定数组 `nums`、键值 `key` 和距离 `k`，找到所有与键值相等且与任意下标距离不超过 `k` 的下标，返回升序排序的列表。找到最小权重。
LightOf
46 0
闻缺陷则喜何志丹
|
7月前
|
算法 测试技术 C#
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
闻缺陷则喜何志丹
47 0
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
ppeua
|
存储 人工智能 算法
【前缀和】截断数组、K倍区间、激光炸弹
现在，要将该数组从中间截断，得到三个非空子数组。
ppeua
86 0
为梦而生~
|
人工智能 BI
【贪心策略】区间选点问题
【贪心策略】区间选点问题
为梦而生~
69 0
小tata鸡米
|
人工智能 算法 BI
贪心算法——区间选点与最大不相交区间数
贪心算法——区间选点与最大不相交区间数
小tata鸡米
79 0
在下小吉.
区间选点（贪心）
这个题，虽然没有写过，但是我盲猜这个题肯定很经典
在下小吉.
112 0

热门文章

最新文章

  • 1
    基于区块链的机器学习模型创建方案
  • 2
    性能的极致,Rust的加持,Zed-Dev编辑器快速搭建Python3.10开发环境
  • 3
    首届Global VR Hackathon完结 全球前三甲诞生
  • 4
    我的博客即将入驻“云栖社区”，诚邀技术同仁一同入驻。
  • 5
    iptables
  • 6
    DevExpress 10.2.4系列-ASPxListBox根据列值不同设置不同图标
  • 7
    jquery的load加载js页面到指定div中
  • 8
    分享平时工作中那些给力的shell命令（更新版）
  • 9
    如何在ubuntu下用SVN commit
  • 10
    hdu 1800 Flying to the Mars
  • 1
    HelloMeme：开源的面部表情与姿态迁移框架，将视频中的人物表情迁移到静态图像中生成动态视频
    100
  • 2
    VSI-Bench：李飞飞谢赛宁团队推出视觉空间智能基准测试集，旨在评估多模态大语言模型在空间认知和理解方面的能力
    31
  • 3
    CLEAR：新加坡国立大学推出线性注意力机制，使8K图像的生成速度提升6.3倍，显著减少了计算量和时间延迟
    31
  • 4
    Kheish：开源的多智能体开发框架，通过 YAML 配置工作流和多个 Agent 共同协作解决复杂任务
    40
  • 5
    Bamba-9B：基于 Mamba2 架构的仅解码语言模型，旨在提高大型语言模型在推理时的效率
    33
  • 6
    DisPose：清华北大等多所高校联合推出基于人物图像增强视频生成技术，实现对人物动画的准确控制和一致性
    31
  • 7
    InvSR：开源图像超分辨率生成模型，提升分辨率，修复老旧照片为超清图像
    29
  • 8
    Univer：开源全栈 AI 办公工具，支持 Word、Excel、PPT 等文档处理和多人实时协作
    24
  • 9
    《人工智能：驱散新材料数据噪声与填补缺失值的曙光》
    21
  • 10
    《人工智能：解锁新材料最佳掺杂元素及比例的密码》
    16

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    DataWorks售前咨询