leetcode算法题之floodfill算法---深搜(dfs)

作者：你好赵伟 | 2024-04-30 20:14:33

踩

本章目录

1.图像渲染
2.岛屿数量
3.岛屿的最大面积
4.被围绕的区域
5.太平洋大西洋水流问题
6.扫雷游戏
7.机器人的运动范围

1.图像渲染

图像渲染
在这里插入图片描述

class Solution {
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    int newColor,prev;
    int m,n;
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        newColor = color;
        prev = image[sr][sc];
        if(color == image[sr][sc]) return image;
        m = image.size(),n = image[0].size();
        dfs(image,sr,sc);
        return image;
    }

    void dfs(vector<vector<int>>& image,int i,int j)
    {
        image[i][j] = newColor;
        for(int k=0;k<4;k++)
        {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&image[x][y] == prev)
            {
                dfs(image,x,y);
            }
        }
    }
};
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

2.岛屿数量

岛屿数量
在这里插入图片描述

class Solution {
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    bool vis[301][301];
    int m,n;
public:
    int numIslands(vector<vector<char>>& 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(!vis[i][j] && grid[i][j] == '1')
                {
                    ret++;
                    dfs(grid,i,j);//把这块区域都标记成已访问
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<char>>& grid,int i,int j)
    {
        vis[i][j] = true;
        for(int k=0;k<4;k++)
        {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&& !vis[x][y]&& grid[x][y] == '1')
            {
                dfs(grid,x,y);
            }
        }
    }
};
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

3.岛屿的最大面积

岛屿的最大面积
在这里插入图片描述

class Solution {
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    int m,n,count;
    bool vis[51][51];
public:
    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(!vis[i][j] && grid[i][j] == 1)
                {
                    count = 0;
                    dfs(grid,i,j);
                    ret = max(ret,count);
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<int>>& grid, int i,int j)
    {
        count++;
        vis[i][j] = true;
        for(int k=0;k<4;k++)
        {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y]&& grid[x][y] == 1)
            {
                dfs(grid,x,y);
            }
        }
    }
};
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

4.被围绕的区域

被围绕的区域
在这里插入图片描述

class Solution {
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    int m,n;
public:
//正难则反：先处理与边缘'O'相连的连通块
    void solve(vector<vector<char>>& board) {
        m = board.size(),n = board[0].size();
        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] == 'O') board[i][j] = 'X';
                else if(board[i][j] == '.') board[i][j] = 'O';
            }
        }
    }
    void dfs(vector<vector<char>>& board,int i,int j)
    {
        board[i][j] = '.';
        for(int k=0;k<4;k++)
        {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n && board[x][y] == 'O')
            {
                dfs(board,x,y);
            }
        }
    }
};
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
40
41

5.太平洋大西洋水流问题

太平洋大西洋水流问题
在这里插入图片描述

class Solution {
//正难则反：求出哪些点能流进太平洋，哪些点能流进大西洋，在求之间的交集即可
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    int m,n;
    vector<vector<bool>> pac;
    vector<vector<bool>> alt;
    vector<vector<int>> ret;
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(),n = heights[0].size();
        pac = vector<vector<bool>>(m,vector<bool>(n));
        alt = vector<vector<bool>>(m,vector<bool>(n));
        for(int i=0;i<m;i++)
        {
            dfs(heights,i,0,pac);
            dfs(heights,i,n-1,alt);
        }
        for(int j=0;j<n;j++)
        {
            dfs(heights,0,j,pac);
            dfs(heights,m-1,j,alt);
        }
        //判断
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(pac[i][j] && alt[i][j])
                {
                    ret.push_back({i,j});
                }
            }
        }
        return ret;
    }

    void dfs(vector<vector<int>>& heights,int i,int j,vector<vector<bool>>& vis)
    {
        vis[i][j] = true;
        for(int k=0;k<4;k++)
        {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && heights[x][y]>=heights[i][j])
            {
                dfs(heights,x,y,vis);
            }
        }
    }
};
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
40
41
42
43
44
45
46
47
48
49
50

6.扫雷游戏

扫雷游戏
在这里插入图片描述

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:
    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;
    }
    void dfs(vector<vector<char>>& board,int i,int j)
    {
        int count =0;
        for(int k=0;k<8;k++)
        {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n && board[x][y] == 'M')
            {
                count++;
            }
        }
        if(count)
        {
            board[i][j] = count +'0';
            return;
        }
        board[i][j] = 'B';
        for(int k=0;k<8;k++)
        {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m &&y>=0 && y<n && board[x][y] == 'E')
            {
                dfs(board,x,y);
            }
        }
    }
};
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
40
41
42
43

7.机器人的运动范围

机器人的运动范围
在这里插入图片描述

class Solution {
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    int m,n,k;
    int ret =0;
    bool vis[101][101];
public:
//从(0，0)点，进行一次深度优先遍历即可
    int movingCount(int _k, int _m, int _n) {
        k = _k,m=_m,n=_n;
        dfs(0,0);
        return ret;
    }
    void dfs(int i,int j)
    {
        ret++;
        vis[i][j] = true;
        for(int k=0;k<4;k++)
        {
            int x = i+dx[k],y = j+dy[k];
            if(x>=0 && x<m&& y>=0 && y<n && !vis[x][y]&& check(x,y))
            {
                dfs(x,y);
            }
        }
    }
    bool check(int x,int y)
    {
        int tmp = 0;
        while(x)
        {
            tmp += x%10;
            x /= 10;
        }
        while(y)
        {
            tmp += y%10;
            y /= 10;
        }
        return tmp<=k;
    }
};
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
40
41
42

这个系列就到处结束啦，希望对大家有所帮助！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/515002