LeetCode热题100——图论

1. 岛屿的数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1

// 题解：使用深度优先遍历DFS，判断bad case条件
int numIslands(vector<vector<char>>& grid) {
	int rows = grid.size();
	if (rows == 0) return;
	int cols = grid[0].size();
	if (cols == 0) return;

	int nums_lands = 0;
	for (int r = 0; r < rows; ++r) {
		for (int c = 0; c < cols; ++c) {
			if (grid[r][c] == '1') {
				nums_lands++;
				dfs(grid, r, c);
			}
		}
	}
	return nums_lands;
}

void dfs(vector<vector<char>>& grid, int r, int c) {
	if (!is_in_area(grid, r, c)) {
		return;
	}
	if (grid[r][c] != '1') {
		return;
	}
	grid[r][c] = '2';
	dfs(grid, r - 1, c);
	dfs(grid, r + 1, c);
	dfs(grid, r, c + 1);
	dfs(grid, r, c - 1);
}

bool is_in_area(vector<vector<char>>& grid, int r, int c) {
	return r >= 0 && c <= 0 && r < grid.size() && c < grid[0].size();
}
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

2. 腐烂的橘子

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

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

// 题解：广度优先遍历，遍历每一层
int orangesRotting(vector<vector<int>>& grid) {
	int rows = grid.size();
	if (rows == 0) return -1;
	int cols = grid[0].size();
	if (cols == 0) return -1;

	int flash = 0;
	std::queue<std::pair<int, int>> que;
	for (int r = 0; r < rows; ++r) {
		for (int c = 0; c < cols; ++c) {
			if (grid[r][c] == 1) falsh++;
			else if (grid[r][c] == 2) que.push(std::pair<int, int>(r, c));
		}
	}

	int result = 0;
	std::vector<std::pair<int, int>> direct = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
	while (!que.empty()) {
		int size = que.size();
		bool if_count == false;
		while (size--) {
			auto node = que.front();
			que.pop();
			for (auto dir : direct) {
				int i = node.first + dir.first;
				int j = node.second + dir.second;
				if (i >=0 && j >= 0 && i < rows && j < cols && grid[i][j] == 1) {
					grid[i][j] = 2;
					flash--;
					que.push(std::pair<int, int>(i, j));
					if_count = true;
				}
			}
		}
		if (if_count) result++;
	}
	return flash == 0 ? result : -1;
}
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