当前位置：首页 > news >正文

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

news 2025/5/31 20:54:15

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<char>>& 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 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);if (c - 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<char>>& 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 的起点，然后按层级（分钟）扩展，让腐烂向四周的新鲜橘子扩散。记录每次扩展花费的时间，直到没有新鲜橘子。

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

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int min = 0, fresh = 0;queue<pair<int, int>> 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<int, int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };while(!q.empty()) {int n = q.size();bool rotten = false;for(int i = 0; i < n; i++) {auto x = q.front();q.pop();for(auto cur: dirs) {int i = x.first + cur.first;int j = x.second + cur.second;if(i >= 0 && i < grid.size() && j >= 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”	多点并行扩散，层次 + 时间计数	最短时间或波及扩散问题