Chapter 17 Graphs (1)
基本题目
797. 所有可能的路径
当前路径记录+回溯+DFS 递归
class Solution {
public:
void dfs(vector<vector<int>>& result, vector<bool> &inPath, vector<int> &path, vector<vector<int>>& graph) {
int pos = path.back();
if (pos == graph.size() - 1) {
result.push_back(path);
return;
}
for (const int &v : graph[pos]) {
if (!inPath[v]) {
path.push_back(v);
inPath[v] = true;
dfs(result, inPath, path, graph);
inPath[v] = false;
path.pop_back();
}
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<bool> inPath(graph.size(), false);
vector<int> path;
vector<vector<int>> result;
path.push_back(0);
inPath[0] = true;
dfs(result, inPath, path, graph);
return result;
}
};
确保不存在环时，可以省略 inPath，不记录节点是否访问过
200. 岛屿数量
DFS 搜索
class Solution {
public:
void search(vector<vector<char>>& grid, vector<vector<bool>>& searched, int i, int j) {
if (searched[i][j]) return;
searched[i][j] = true;
if (grid[i][j] == '0') return;
int m = grid.size(), n = grid[0].size();
if (i > 0) search(grid, searched, i - 1, j);
if (j < n - 1) search(grid, searched, i, j + 1);
if (i < m - 1) search(grid, searched, i + 1, j);
if (j > 0) search(grid, searched, i, j - 1);
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> searched(m, vector<bool>(n, false));
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!searched[i][j]) {
if (grid[i][j] == '1') count++;
search(grid, searched, i, j);
}
}
}
return count;
}
};
BFS 搜索
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> searched(m, vector<bool>(n, false));
int count = 0;
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!searched[i][j]) {
searched[i][j] = true;
if (grid[i][j] == '1') {
count++;
q.push({i, j});
while (!q.empty()) {
pair<int, int> pos = q.front();
q.pop();
int r = pos.first, c = pos.second;
if (grid[r][c] == '1') {
if (r > 0 && !searched[r - 1][c]) {
q.push({r - 1, c});
searched[r - 1][c] = true;
}
if (c < n - 1 && !searched[r][c + 1]) {
q.push({r, c + 1});
searched[r][c + 1] = true;
}
if (r < m - 1 && !searched[r + 1][c]) {
q.push({r + 1, c});
searched[r + 1][c] = true;
}
if (c > 0 && !searched[r][c - 1]) {
q.push({r, c - 1});
searched[r][c - 1] = true;
}
}
}
}
}
}
}
return count;
}
};
本题还可以转化为并查集问题，会在后续题目中探讨
695. 岛屿的最大面积
与 200. 岛屿数量 基本一致，在搜索过程中维护岛屿面积
可以采用递归 DFS、迭代 DFS、迭代 BFS
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> searched(m, vector<bool>(n, false));
int maxArea = 0;
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!searched[i][j]) {
searched[i][j] = true;
if (grid[i][j]) {
int area = 0;
q.push({i, j});
while (!q.empty()) {
pair<int, int> pos = q.front();
q.pop();
int r = pos.first, c = pos.second;
if (grid[r][c]) {
area++;
if (r > 0 && !searched[r - 1][c]) {
q.push({r - 1, c});
searched[r - 1][c] = true;
}
if (c < n - 1 && !searched[r][c + 1]) {
q.push({r, c + 1});
searched[r][c + 1] = true;
}
if (r < m - 1 && !searched[r + 1][c]) {
q.push({r + 1, c});
searched[r + 1][c] = true;
}
if (c > 0 && !searched[r][c - 1]) {
q.push({r, c - 1});
searched[r][c - 1] = true;
}
}
}
maxArea = max(maxArea, area);
}
}
}
}
return maxArea;
}
};
1020. 飞地的数量
同前几题，在 DFS/BFS 的过程中判断该区域是否有效，仅当有效时再加到结果中
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int total = 0;
queue<pair<int, int>> q;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j]) {
grid[i][j] = 0;
int area = 0, valid = 1;
q.push({i, j});
while (!q.empty()) {
area++;
pair<int, int> pos = q.front();
q.pop();
int r = pos.first, c = pos.second;
if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
valid = 0;
}
if (r > 0 && grid[r - 1][c]) {
q.push({r - 1, c});
grid[r - 1][c] = 0;
}
if (c < n - 1 && grid[r][c + 1]) {
q.push({r, c + 1});
grid[r][c + 1] = 0;
}
if (r < m - 1 && grid[r + 1][c]) {
q.push({r + 1, c});
grid[r + 1][c] = 0;
}
if (c > 0 && grid[r][c - 1]) {
q.push({r, c - 1});
grid[r][c - 1] = 0;
}
}
total += area * valid;
}
}
}
return total;
}
};
130. 被围绕的区域
同前几题，在 DFS/BFS 的过程中判断该区域是否有效，有效时标记该区域所有位置
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size(), n = board[0].size();
vector<vector<bool>> searched(m, vector<bool>(n, false));
queue<pair<int, int>> q;
vector<pair<int, int>> region;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!searched[i][j] && board[i][j] == 'O') {
int area = 0, valid = 1;
q.push({i, j});
searched[i][j] = true;
while (!q.empty()) {
pair<int, int> pos = q.front();
q.pop();
int r = pos.first, c = pos.second;
if (board[r][c] == 'O') {
region.push_back(pos);
if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
valid = 0;
}
if (r > 0 && !searched[r - 1][c]) {
q.push({r - 1, c});
searched[r - 1][c] = true;
}
if (c < n - 1 && !searched[r][c + 1]) {
q.push({r, c + 1});
searched[r][c + 1] = true;
}
if (r < m - 1 && !searched[r + 1][c]) {
q.push({r + 1, c});
searched[r + 1][c] = true;
}
if (c > 0 && !searched[r][c - 1]) {
q.push({r, c - 1});
searched[r][c - 1] = true;
}
}
}
if (valid) {
for (const pair<int, int> &pos : region) {
board[pos.first][pos.second] = 'X';
}
}
region.clear();
}
}
}
}
};
可以从判断有效的规则出发：先考虑边界的方格，将那些区域标记即可
class Solution {
public:
void dfs(vector<vector<char>>& result, vector<vector<char>>& board, int i, int j) {
int m = board.size(), n = board[0].size();
if (i < 0 || i >= m || j < 0 || j >= n) return;
if (result[i][j] == 'O' || board[i][j] == 'X') return;
result[i][j] = 'O';
dfs(result, board, i - 1, j);
dfs(result, board, i + 1, j);
dfs(result, board, i, j - 1);
dfs(result, board, i, j + 1);
}
void solve(vector<vector<char>>& board) {
int m = board.size(), n = board[0].size();
vector<vector<char>> result(m, vector<char>(n, 'X'));
for (int i = 0; i < m; i++) {
dfs(result, board, i, 0);
dfs(result, board, i, n - 1);
}
for (int j = 0; j < n; j++) {
dfs(result, board, 0, j);
dfs(result, board, m - 1, j);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = result[i][j];
}
}
}
};
417. 太平洋大西洋水流问题
起点不明确但终点明确：从终点出发搜索
class Solution {
public:
void dfs(vector<vector<int>>& heights, vector<vector<bool>>& reachable, int i, int j) {
if (reachable[i][j]) return;
reachable[i][j] = true;
int m = heights.size(), n = heights[0].size();
if (i > 0 && heights[i - 1][j] >= heights[i][j]) dfs(heights, reachable, i - 1, j);
if (i < m - 1 && heights[i + 1][j] >= heights[i][j]) dfs(heights, reachable, i + 1, j);
if (j > 0 && heights[i][j - 1] >= heights[i][j]) dfs(heights, reachable, i, j - 1);
if (j < n - 1 && heights[i][j + 1] >= heights[i][j]) dfs(heights, reachable, i, j + 1);
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) dfs(heights, pacific, i, 0);
for (int j = 0; j < n; j++) dfs(heights, pacific, 0, j);
for (int i = 0; i < m; i++) dfs(heights, atlantic, i, n - 1);
for (int j = 0; j < n; j++) dfs(heights, atlantic, m - 1, j);
vector<vector<int>> result;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.push_back({i, j});
}
}
}
return result;
}
};
827. 最大人工岛
先计算每个格子所属的岛屿及面积，后遍历空格计算最大值
class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> islandIdx(m, vector<int>(n, -1));
vector<int> islandSizes;
queue<pair<int, int>> q;
int id = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] && islandIdx[i][j] < 0) {
int size = 0;
q.push({i, j});
islandIdx[i][j] = id;
while (!q.empty()) {
pair<int, int> pos = q.front();
q.pop();
int r = pos.first, c = pos.second;
if (!grid[r][c]) continue;
size++;
if (r > 0 && grid[r - 1][c] && islandIdx[r - 1][c] < 0) {
q.push({r - 1, c});
islandIdx[r - 1][c] = id;
}
if (c < n - 1 && grid[r][c + 1] && islandIdx[r][c + 1] < 0) {
q.push({r, c + 1});
islandIdx[r][c + 1] = id;
}
if (r < m - 1 && grid[r + 1][c] && islandIdx[r + 1][c] < 0) {
q.push({r + 1, c});
islandIdx[r + 1][c] = id;
}
if (c > 0 && grid[r][c - 1] && islandIdx[r][c - 1] < 0) {
q.push({r, c - 1});
islandIdx[r][c - 1] = id;
}
}
islandSizes.push_back(size);
id++;
}
}
}
int maxSize = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (islandIdx[i][j] < 0) {
int size = 1;
unordered_set<int> s;
if (i > 0 && islandIdx[i - 1][j] >= 0 && !s.count(islandIdx[i - 1][j])) {
s.insert(islandIdx[i - 1][j]);
size += islandSizes[islandIdx[i - 1][j]];
}
if (j > 0 && islandIdx[i][j - 1] >= 0 && !s.count(islandIdx[i][j - 1])) {
s.insert(islandIdx[i][j - 1]);
size += islandSizes[islandIdx[i][j - 1]];
}
if (i < m - 1 && islandIdx[i + 1][j] >= 0 && !s.count(islandIdx[i + 1][j])) {
s.insert(islandIdx[i + 1][j]);
size += islandSizes[islandIdx[i + 1][j]];
}
if (j < n - 1 && islandIdx[i][j + 1] >= 0 && !s.count(islandIdx[i][j + 1])) {
s.insert(islandIdx[i][j + 1]);
size += islandSizes[islandIdx[i][j + 1]];
}
maxSize = max(maxSize, size);
}
}
}
if (maxSize == 0) return islandSizes[0];
return maxSize;
}
};