目录
FloodFill算法：从一个起始位置开始，找性质相同的连通块。
1. 图像渲染（简单）
题目描述有问题，所谓“像素值”就是指该像素点的颜色。
先让初始坐标上色，再让其上下左右的坐标上色。
1.1 BFS
先让初始坐标(sr, sc)入队并上色，队列中：(sr, sc)
让(sr, sc)出队，让(sr, sc)的上下左右入队并上色（假设都满足条件），队列中：(sr, sc)(sr-1, sc)(sr+1, sc)(sr, sc-1)(sr, sc+1)
让(sr-1, sc)(sr+1, sc)(sr, sc-1)(sr, sc+1)出队，让它们各自的上下左右入队并上色（假设都满足条件），队列中：是刚才出队的坐标的上下左右
……
直到队列为空，BFS结束。
注意入队的坐标要满足条件：不能越界且颜色和初始坐标的颜色相同。
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
clr = image[sr][sc];
if (clr == color) // 不修改颜色
return image;
m = image.size();
n = image[0].size();
bfs(image, sr, sc, color);
return image;
}
private:
void bfs(vector<vector<int>>& image, int r, int c, int color)
{
queue<pair<int, int>> q;
// 初始坐标入队并上色
q.push({r, c});
image[r][c] = color;
while (!q.empty())
{
// 队头出队
auto [row, col] = q.front();
q.pop();
// 判断刚才出队的坐标上下左右是否满足条件，满足条件则入队并上色
for (int i = 0; i < 4; i++)
{
int x = row + dr[i];
int y = col + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == clr)
{
q.push({x, y});
image[x][y] = color;
}
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
int clr; // 初始的颜色
};1.2 DFS
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
clr = image[sr][sc];
if (clr == color) // 不修改颜色
return image;
m = image.size();
n = image[0].size();
dfs(image, sr, sc, color);
return image;
}
private:
void dfs(vector<vector<int>>& image, int r, int c, int color)
{
// 初始坐标上色
image[r][c] = color;
// 判断初始坐标上下左右是否满足条件，满足条件则递归上色
for (int i = 0; i < 4; i++)
{
int x = r + dr[i];
int y = c + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == clr)
{
dfs(image, x, y, color);
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
int clr; // 初始的颜色
};2. 岛屿数量（中等）
创建一个和原二维数组大小相等的二维数组visited，用来标记坐标是否被访问过。
遍历二维数组，遇到没访问过的'1'，则以它为起始坐标向周围扩散，这就是一个岛屿，并且岛屿要被标记。
2.1 BFS
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
m = grid.size();
n = grid[0].size();
visited.resize(m, vector<bool>(n));
int ans = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '1' && !visited[i][j])
{
ans++;
bfs(grid, i, j); // 把这块岛屿全部标记一下
}
}
}
return ans;
}
private:
void bfs(vector<vector<char>>& grid, int r, int c)
{
queue<pair<int, int>> q;
// 初始坐标入队并标记
q.push({r, c});
visited[r][c] = true;
while (!q.empty())
{
// 队头出队
auto [row, col] = q.front();
q.pop();
// 判断刚才出队的坐标上下左右是否满足条件，满足条件则入队并标记
for (int i = 0; i < 4; i++)
{
int x = row + dr[i];
int y = col + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !visited[x][y])
{
q.push({x, y});
visited[x][y] = true;
}
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
vector<vector<bool>> visited; // 标记坐标是否被访问过
};2.2 DFS
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
m = grid.size();
n = grid[0].size();
visited.resize(m, vector<bool>(n));
int ans = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '1' && !visited[i][j])
{
ans++;
dfs(grid, i, j); // 把这块岛屿全部标记一下
}
}
}
return ans;
}
private:
void dfs(vector<vector<char>>& grid, int r, int c)
{
// 初始坐标标记访问
visited[r][c] = true;
// 判断初始坐标上下左右是否满足条件，满足条件则递归标记访问
for (int i = 0; i < 4; i++)
{
int x = r + dr[i];
int y = c + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !visited[x][y])
{
dfs(grid, x, y);
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
vector<vector<bool>> visited; // 标记坐标是否被访问过
};3. 岛屿的最大面积（中等）
3.1 BFS
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
visited.resize(m, vector<bool>(n));
int ans = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1 && !visited[i][j])
{
ans = max(ans, bfs(grid, i, j));
}
}
}
return ans;
}
private:
int bfs(vector<vector<int>>& grid, int r, int c)
{
int area = 0; // 这块岛屿的面积
queue<pair<int, int>> q;
// 初始坐标入队并标记并且面积++
q.push({r, c});
visited[r][c] = true;
area++;
while (!q.empty())
{
// 队头出队
auto [row, col] = q.front();
q.pop();
// 判断刚才出队的坐标上下左右是否满足条件，满足条件则入队并标记并且面积++
for (int i = 0; i < 4; i++)
{
int x = row + dr[i];
int y = col + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !visited[x][y])
{
q.push({x, y});
visited[x][y] = true;
area++;
}
}
}
return area;
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
vector<vector<bool>> visited; // 标记坐标是否被访问过
};3.2 DFS
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
visited.resize(m, vector<bool>(n));
int ans = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 1 && !visited[i][j])
{
ans = max(ans, dfs(grid, i, j));
}
}
}
return ans;
}
private:
int dfs(vector<vector<int>>& grid, int r, int c)
{
int area = 0; // 这块岛屿的面积
// 初始坐标标记访问
visited[r][c] = true;
area++;
// 判断初始坐标上下左右是否满足条件，满足条件则递归标记访问
for (int i = 0; i < 4; i++)
{
int x = r + dr[i];
int y = c + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !visited[x][y])
{
area += dfs(grid, x, y);
}
}
return area;
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
vector<vector<bool>> visited; // 标记坐标是否被访问过
};4. 被围绕的区域（中等）
先处理边界上的'O'连通块，把它们修改成非'O'非'X'的字符，例如字符'a'。
再遍历矩阵，如果遍历到'a'，说明它属于边界上的'O'连通块，把'a'还原成'O'；如果遍历到'O'，说明它属于被'X'围绕的'O'连通块，把'O'修改成'X'。
4.1 BFS
class Solution {
public:
void solve(vector<vector<char>>& board) {
m = board.size();
n = board[0].size();
// 先处理边界上的'O'连通块
for (int i = 0; i < m; i++)
{
if (board[i][0] == 'O')
{
bfs(board, i, 0);
}
if (board[i][n - 1] == 'O')
{
bfs(board, i, n - 1);
}
}
for (int j = 0; j < n; j++)
{
if (board[0][j] == 'O')
{
bfs(board, 0, j);
}
if (board[m - 1][j] == 'O')
{
bfs(board, m - 1, j);
}
}
// 再遍历矩阵，修改
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 'a')
{
board[i][j] = 'O';
}
else if (board[i][j] == 'O')
{
board[i][j] = 'X';
}
}
}
}
private:
void bfs(vector<vector<char>>& board, int r, int c)
{
queue<pair<int, int>> q;
// 初始坐标入队并修改元素值
q.push({r, c});
board[r][c] = 'a';
while (!q.empty())
{
// 队头出队
auto [row, col] = q.front();
q.pop();
// 判断刚才出队的坐标上下左右是否满足条件，满足条件则入队并修改元素值
for (int i = 0; i < 4; i++)
{
int x = row + dr[i];
int y = col + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
{
q.push({x, y});
board[x][y] = 'a';
}
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
};4.2 DFS
class Solution {
public:
void solve(vector<vector<char>>& board) {
m = board.size();
n = board[0].size();
// 先处理边界上的'O'连通块
for (int i = 0; i < m; i++)
{
if (board[i][0] == 'O')
{
dfs(board, i, 0);
}
if (board[i][n - 1] == 'O')
{
dfs(board, i, n - 1);
}
}
for (int j = 0; j < n; j++)
{
if (board[0][j] == 'O')
{
dfs(board, 0, j);
}
if (board[m - 1][j] == 'O')
{
dfs(board, m - 1, j);
}
}
// 再遍历矩阵，修改
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (board[i][j] == 'a')
{
board[i][j] = 'O';
}
else if (board[i][j] == 'O')
{
board[i][j] = 'X';
}
}
}
}
private:
void dfs(vector<vector<char>>& board, int r, int c)
{
// 初始坐标修改元素值
board[r][c] = 'a';
// 判断初始坐标上下左右是否满足条件，满足条件则递归修改元素值
for (int i = 0; i < 4; i++)
{
int x = r + dr[i];
int y = c + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
{
dfs(board, x, y);
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
};5. 飞地的数量（中等）
和上一题“被围绕的区域”类似。
先处理边界上的1连通块，把它们修改成非0非1的整型，例如2。
再遍历矩阵，如果遍历到2，说明它属于边界上的1连通块，把2还原成1；如果遍历到1，说明它属于被0围绕的1连通块，计算数量。
5.1 BFS
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
// 先处理边界上的1连通块
for (int i = 0; i < m; i++)
{
if (grid[i][0] == 1)
{
bfs(grid, i, 0);
}
if (grid[i][n - 1] == 1)
{
bfs(grid, i, n - 1);
}
}
for (int j = 0; j < n; j++)
{
if (grid[0][j] == 1)
{
bfs(grid, 0, j);
}
if (grid[m - 1][j] == 1)
{
bfs(grid, m - 1, j);
}
}
// 再遍历矩阵，遍历到2则修改成1，遍历到1则计数
int ans = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 2)
{
grid[i][j] = 1;
}
else if (grid[i][j] == 1)
{
ans++;
}
}
}
return ans;
}
private:
void bfs(vector<vector<int>>& grid, int r, int c)
{
queue<pair<int, int>> q;
// 初始坐标入队并修改元素值
q.push({r, c});
grid[r][c] = 2;
while (!q.empty())
{
// 队头出队
auto [row, col] = q.front();
q.pop();
// 判断刚才出队的坐标上下左右是否满足条件，满足条件则入队并修改元素值
for (int i = 0; i < 4; i++)
{
int x = row + dr[i];
int y = col + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
{
q.push({x, y});
grid[x][y] = 2;
}
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
};5.2 DFS
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
m = grid.size();
n = grid[0].size();
// 先处理边界上的1连通块
for (int i = 0; i < m; i++)
{
if (grid[i][0] == 1)
{
dfs(grid, i, 0);
}
if (grid[i][n - 1] == 1)
{
dfs(grid, i, n - 1);
}
}
for (int j = 0; j < n; j++)
{
if (grid[0][j] == 1)
{
dfs(grid, 0, j);
}
if (grid[m - 1][j] == 1)
{
dfs(grid, m - 1, j);
}
}
// 再遍历矩阵，遍历到2则修改成1，遍历到1则计数
int ans = 0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == 2)
{
grid[i][j] = 1;
}
else if (grid[i][j] == 1)
{
ans++;
}
}
}
return ans;
}
private:
void dfs(vector<vector<int>>& grid, int r, int c)
{
// 初始坐标修改元素值
grid[r][c] = 2;
// 判断初始坐标上下左右是否满足条件，满足条件则递归修改元素值
for (int i = 0; i < 4; i++)
{
int x = r + dr[i];
int y = c + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1)
{
dfs(grid, x, y);
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
};6. 太平洋大西洋水流问题（中等）
正难则反。如果直接去判断某个坐标的雨水是否既能流到太平洋又能流到大西洋，会重复遍历每个坐标。我们可以从矩阵的边界开始反向搜索寻找雨水流向边界的单元格，反向搜索时，每次只能移动到高度相同或更大的单元格。
从太平洋沿岸反向搜索，标记雨水可以流向太平洋的坐标；从大西洋沿岸反向搜索，标记雨水可以流向大西洋的坐标。那么，被标记两次的坐标，就是我们要找的结果。
6.1 BFS
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
m = heights.size();
n = heights[0].size();
vector<vector<bool>> pac(m, vector<bool>(n)); // 标记雨水能否流到太平洋
vector<vector<bool>> atl(m, vector<bool>(n)); // 标记雨水能否流到大西洋
// 从太平洋沿岸搜索
for (int i = 0; i < m; i++)
{
bfs(heights, i, 0, pac);
}
for (int j = 0; j < n; j++)
{
bfs(heights, 0, j, pac);
}
// 从大西洋沿岸搜索
for (int i = 0; i < m; i++)
{
bfs(heights, i, n - 1, atl);
}
for (int j = 0; j < n; j++)
{
bfs(heights, m - 1, j, atl);
}
vector<vector<int>> ans;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (pac[i][j] && atl[i][j])
{
ans.push_back({i, j});
}
}
}
return ans;
}
private:
void bfs(vector<vector<int>>& heights, int r, int c, vector<vector<bool>>& visited)
{
queue<pair<int, int>> q;
// 初始坐标入队并标记访问
q.push({r, c});
visited[r][c] = true;
while (!q.empty())
{
// 队头出队
auto [row, col] = q.front();
q.pop();
// 判断刚才出队的坐标上下左右是否满足条件，满足条件则入队并标记访问
for (int i = 0; i < 4; i++)
{
int x = row + dr[i];
int y = col + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && heights[x][y] >= heights[row][col])
{
q.push({x, y});
visited[x][y] = true;
}
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
};6.2 DFS
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
m = heights.size();
n = heights[0].size();
vector<vector<bool>> pac(m, vector<bool>(n)); // 标记雨水能否流到太平洋
vector<vector<bool>> atl(m, vector<bool>(n)); // 标记雨水能否流到大西洋
// 从太平洋沿岸搜索
for (int i = 0; i < m; i++)
{
dfs(heights, i, 0, pac);
}
for (int j = 0; j < n; j++)
{
dfs(heights, 0, j, pac);
}
// 从大西洋沿岸搜索
for (int i = 0; i < m; i++)
{
dfs(heights, i, n - 1, atl);
}
for (int j = 0; j < n; j++)
{
dfs(heights, m - 1, j, atl);
}
vector<vector<int>> ans;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (pac[i][j] && atl[i][j])
{
ans.push_back({i, j});
}
}
}
return ans;
}
private:
void dfs(vector<vector<int>>& heights, int r, int c, vector<vector<bool>>& visited)
{
// 初始坐标标记访问
visited[r][c] = true;
// 判断初始坐标上下左右是否满足条件，满足条件则递归标记访问
for (int i = 0; i < 4; i++)
{
int x = r + dr[i];
int y = c + dc[i];
if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && heights[x][y] >= heights[r][c])
{
dfs(heights, x, y, visited);
}
}
}
// 坐标上下左右的偏移量
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int m;
int n;
};