LeetCode-图论-岛屿数量+腐烂的橘子_岛屿问题相关coding

LeetCode-图论-岛屿数量+腐烂的橘子

✏️ 关于专栏：专栏用于记录 prepare for the coding test。

---

文章目录

• LeetCode-图论-岛屿数量+腐烂的橘子
• • 📝 岛屿数量
  • • 🎯题目描述
    • 🔍 输入输出示例
    • 🧩题目提示
    • 🧪AC
  • 📝 腐烂的橘子
  • • 🎯题目描述
    • 🔍 输入输出示例
    • 🧩题目提示
    • 🧪AC
  • 🌟 总结

📝 岛屿数量

🎯题目描述

给你一个由 \'1\'（陆地）和 \'0\'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

🔗题目链接：岛屿数量

🔍 输入输出示例

示例 1:

输入：grid = [ [\"1\",\"1\",\"1\",\"1\",\"0\"], [\"1\",\"1\",\"0\",\"1\",\"0\"], [\"1\",\"1\",\"0\",\"0\",\"0\"], [\"0\",\"0\",\"0\",\"0\",\"0\"]]输出：1

示例 2:

输入：grid = [ [\"1\",\"1\",\"0\",\"0\",\"0\"], [\"1\",\"1\",\"0\",\"0\",\"0\"], [\"0\",\"0\",\"1\",\"0\",\"0\"], [\"0\",\"0\",\"0\",\"1\",\"1\"]]输出：3

🧩题目提示

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 \'0\' 或 \'1\'

🧪AC

1.遍历整个网格；

2.每次遇到一个 \'1\'（陆地）：

• 计数器 +1（代表新发现一个岛屿）；
• 调用 DFS，将与该陆地连接的所有 \'1\' 都标记为 \'0\'（沉岛）；

3.遍历完后得到岛屿数量。

class Solution {private: void dfs(vector<vector>& grid, int r, int c) { int nr = grid.size(); int nc = grid[0].size(); grid[r][c] = \'0\'; if (r - 1 >= 0 && grid[r-1][c] == \'1\') dfs(grid, r - 1, c); if (r + 1 = 0 && grid[r][c-1] == \'1\') dfs(grid, r, c - 1); if (c + 1 < nc && grid[r][c+1] == \'1\') dfs(grid, r, c + 1); }public: int numIslands(vector<vector>& grid) { int nr = grid.size(); if (!nr) return 0; int nc = grid[0].size(); int num_islands = 0; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == \'1\') {  ++num_islands;  dfs(grid, r, c); } } } return num_islands; }};

📝 腐烂的橘子

🎯题目描述

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

🔗题目链接：腐烂的橘子

🔍 输入输出示例

示例 1:

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]输出：4

示例 2:

输入：grid = [[0,2]]输出：0解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

🧩题目提示

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] 仅为 0、1 或 2

🧪AC

将每个腐烂的橘子当作BFS 的起点，然后按层级（分钟）扩展，让腐烂向四周的新鲜橘子扩散。记录每次扩展花费的时间，直到没有新鲜橘子。

1. 初始化变量：
   • 统计新鲜橘子数量 fresh；
   • 将所有腐烂橘子的坐标加入队列 queue；
   • 设置 minutes = 0 表示经过的分钟数。
2. 开始 BFS：
   • 使用队列进行 BFS，每一轮代表 1 分钟；
   • 对队列中每个腐烂橘子，向四个方向传播腐烂；
   • 将接触到的新鲜橘子标记为腐烂，并加入队列；
   • 每轮 BFS 结束后，如果确实腐烂了橘子，则 minutes++。
3. 检查是否有剩余新鲜橘子：
   • 如果最后仍有新鲜橘子未被腐烂，说明无法全部腐烂，返回 -1；
   • 否则，返回 minutes。

class Solution {public: int orangesRotting(vector<vector>& grid) { int min = 0, fresh = 0; queue<pair> q; for(int i = 0; i < grid.size(); i++) { for(int j = 0; j < grid[0].size(); j++) if(grid[i][j] == 1) fresh++; else if(grid[i][j] == 2) q.push({i, j}); } vector<pair> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; while(!q.empty()) { int n = q.size(); bool rotten = false; for(int i = 0; i = 0 && i = 0 && j < grid[0].size() && grid[i][j] == 1) { grid[i][j] = 2; q.push({i, j}); fresh--; rotten = true;  } } } if(rotten) min++; } return fresh ? -1 : min; }};

🌟 总结

题目 解法类型 搜索方式 应用图论模型 关键点 最佳使用场景 岛屿数量 DFS / BFS 连通块计数 无权无向图遍历 沉岛处理，标记访问，连通块数量 静态图的连通性判断 腐烂的橘子 BFS 层序遍历 拓展过程的“多源BFS” 多点并行扩散，层次 + 时间计数 最短时间或波及扩散问题

🧩DFS 沉岛，BFS 扩散，方向数组要牢记；剪枝越界要及时，复杂度稳中取胜！

❤️ 如果对你有帮助，别忘了点赞、收藏支持一下，我将持续更新更多高质量刷题笔记！
📘 点击查看 👉 算法笔记专栏：Prepare for the Coding Test

摄影技巧分享