前言
大家好，我是jiantaoyab，在下面的题目中慢慢体会floodFill算法，虽然是新的算法，但是用的思想和前面的文章几乎一样，代码格式也几乎一样，但不要去背代码
图像渲染
https://leetcode.cn/problems/flood-fill/
解析
代码
可以看到代码这部分，是不是和前面的文章的挺像的
class Solution {
int m, n;
int pre_color;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
public:
void dfs(vector<vector<int>>& image, int sr, int sc, int color)
{
image[sr][sc] = color;
for(int d = 0; d < 4; d++)
{
int x = sr + dx[d], y = sc + dy[d];
if((x >= 0 && x < m) && (y >= 0 && y < n) && image[x][y] == pre_color)
{
image[x][y] = color;
dfs(image, x, y, color);
}
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
m = image.size(), n = image[0].size();
pre_color = image[sr][sc];
if(image[sr][sc] == color) return image;
dfs(image, sr, sc, color);
return image;
}
};
岛屿数量
https://leetcode.cn/problems/number-of-islands/
解析
代码
class Solution {
int m, n;
vector<vector<bool>> check;
int dx[4]= {0, 0, 1, -1};
int dy[4]= {1, -1, 0, 0};
public:
void dfs(vector<vector<char>>& grid, int i, int j)
{
check[i][j] = true; //从i，j位置来的
for(int d = 0; d < 4; d++)
{
int x = i + dx[d], y = j + dy[d];
if((x >= 0 && x < m) && (y >= 0 && y < n) && grid[x][y] == '1' && !check[x][y])
{
dfs(grid, x, y);
}
}
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
check = vector<vector<bool>> (m ,vector<bool>(n));
int ret = 0;
//把整个grid遍历一次
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
//如果是一个岛屿而且是没有出现过的
if(grid[i][j] == '1' && !check[i][j])
{
ret++;
dfs(grid, i, j);
}
}
}
return ret;
}
};
岛屿的最大面积
https://leetcode.cn/problems/ZL6zAn/
解析
大家看这个图就知道题目求的是什么了，比起上一题，多个统计数
代码
class Solution {
int m, n;
bool check[51][51];
int dx[4] = {1,-1,0,0};
int dy[4] = {0, 0,1,-1};
int count;
public:
void dfs(vector<vector<int>>& grid, int i, int j)
{
count++;
check[i][j] = true;
for(int d = 0; d < 4; d++)
{
int x = i + dx[d], y = j + dy[d];
if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !check[x][y])
{
dfs(grid, x, y);
}
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
int ret = 0;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(!check[i][j] && grid[i][j] == 1)
{
count = 0;
dfs(grid, i, j);
ret = max(ret, count);
}
}
}
return ret;
}
};
被围绕的区域
https://leetcode.cn/problems/surrounded-regions/
解析
代码
class Solution {
int m, n;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
public:
void dfs(vector<vector<char>>& board, int i, int j)
{
board[i][j] = 'a';
for(int d = 0; d < 4; d++)
{
int x = i + dx[d], y = j + dy[d];
if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
{
dfs(board, x, y);
}
}
}
void solve(vector<vector<char>>& board) {
m = board.size(), n = board[0].size();
//把左右2列边界处理了
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);
}
//把上下2行边界处理了
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';
}
}
}
};
太平洋大西洋水流问题
https://leetcode.cn/problems/pacific-atlantic-water-flow/
解析
代码
class Solution {
int m, n;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
public:
void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>&check)
{
check[i][j] = true;
for(int d = 0; d < 4; d++)
{
int x = i + dx[d], y = j + dy[d];
if(x >= 0 && x < m && y >= 0 && y < n && !check[x][y] &&heights[x][y] >= heights[i][j] )
{
dfs(heights, x, y, check);
}
}
}
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));
//处理pac
for(int j = 0; j < n; j++) dfs(heights, 0, j, pac);
for(int i = 0; i < m; i++) dfs(heights, i, 0, pac);
//处理alt
for(int j = 0; j < n; j++) dfs(heights, m - 1, j, atl);
for(int i = 0; i < m; i++) dfs(heights, i, n - 1, atl);
vector<vector<int>> ret;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(pac[i][j] && atl[i][j])
ret.push_back({i, j});
}
}
return ret;
}
};
扫雷游戏
https://leetcode.cn/problems/minesweeper/
解析
代码
class Solution {
int dx[8] = {0, 0, -1, 1, 1, 1, -1 ,-1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1 ,-1};
int m, n;
public:
void dfs(vector<vector<char>>& board, int i, int j)
{
int count = 0; //地雷个数
//统计地雷个数
for(int d = 0; d < 8; d++)
{
int x = i + dx[d], y = j + dy[d];
if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M')
{
count++;
}
}
//周围有地雷
if(count)
{
board[i][j] = count + '0';
return ;
}
//周围没地雷展开
else
{
board[i][j] = 'B';
for(int d = 0; d < 8; d++)
{
int x = i + dx[d], y = j + dy[d];
if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
{
dfs(board, x, y);
}
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
m = board.size(), n = board[0].size();
int x = click[0], y = click[1];
//开局中地雷
if(board[x][y] == 'M')
{
board[x][y] = 'X';
return board;
}
dfs(board, x, y);
return board;
}
};
