【算法积累】LeetCode的三道DFS题目

怼烎@ 2022-08-29 00:23 90阅读 0赞

# LeetCode 200 - 岛屿数量（中等） #

[题目链接][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]

> 注意DFS的条件判断，不然会因为无限递归而Stack Overflow。

语言：C++

class Solution { 
    public:
        const int di[4][2] = { { 0, 1}, { 0, -1}, { 1, 0}, { -1, 0}};
    
        void dfs(vector<vector<char>>& grid, int x, int y) { 
            int r = grid.size();
            int c = grid[0].size();
            if (grid[x][y] == '1') { 
                grid[x][y] = '0';
                for (auto & i : di) { 
                    int next_x = i[0] + x;
                    int next_y = i[1] + y;
                    if (next_x >= 0 && next_x < r && next_y >= 0 && next_y < c) { 
                        dfs(grid, next_x, next_y);
                    }
                }
            }    
        }
    
        int numIslands(vector<vector<char>>& grid) { 
            int r = grid.size();
            int c = grid[0].size();
            int ans = 0;
            for (int i = 0; i < r; i++) { 
                for (int j = 0; j < c; j++) { 
                    if (grid[i][j] == '1') { 
                        ans++;
                        dfs(grid, i, j);
                    }
                }
            }
            return ans;
        }
    };

# LeetCode 695 - 岛屿的最大面积（中等） #

[题目链接][Link 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 1]  
语言：C++

class Solution { 
    public:
        const int di[4][2] = { { 0, 1}, { 1, 0}, { 0, -1}, { -1, 0}};
    
        int dfs(vector<vector<int>>& grid, int x, int y) { 
            if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] != 1) { 
                return 0;
            }
            grid[x][y] = 0;
            int ans = 1;
            for (auto & i : di) { 
                int x_next = x + i[0];
                int y_next = y + i[1];
                ans += dfs(grid, x_next, y_next);
            }
            return ans;
        }
    
        int maxAreaOfIsland(vector<vector<int>>& grid) { 
            int ans = 0;
            for (int i = 0; i < grid.size(); i++) { 
                for (int j = 0; j < grid[0].size(); j++) { 
                    ans = max(ans, dfs(grid, i, j));
                }
            }
            return ans;
        }
    };

# LeetCode 733 - 图像渲染（简单） #

[题目链接][Link 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 2]

> 和上面的LeetCode 200一样，需要注意DFS的条件判断，不然会因为无限递归而Stack Overflow。

语言：C++

class Solution { 
    public:
        const int di[4][2] = { { 0, 1}, { 0, -1}, { -1, 0}, { 1, 0}};
    
        void dfs(vector<vector<int>>& image, int x, int y, int oldColor, int newColor) { 
            if (image[x][y] == oldColor) { 
                image[x][y] = newColor;
                for (auto & i : di) { 
                    int x_next = i[0] + x;
                    int y_next = i[1] + y;
                    if (x_next >= 0 && y_next >= 0 && x_next < image.size() && y_next < image[0].size()) { 
                        dfs(image, x_next, y_next, oldColor, newColor);
                    }
                }
            }
        }
    
        vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) { 
            int oldColor = image[sr][sc];
            if (oldColor != newColor) { 
                dfs(image, sr, sc, oldColor, newColor);
            }
            return image;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/number-of-islands/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]: /images/20220829/41c18b8492594a80a5fb9498c906f4a0.png
[Link 2]: https://leetcode-cn.com/problems/max-area-of-island/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 1]: /images/20220829/ca28d0c4eaba4fe1910473b0438b96ef.png
[Link 3]: https://leetcode-cn.com/problems/flood-fill/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 2]: /images/20220829/aa3e842b38924f27b6fbab5037bd97e3.png