bfs and dfs


  • 0
    X
    class Solution {
    public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max_area = 0;
        
        for (int i = 0; i != grid.size(); i++) {
            for (int j = 0; j != grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    max_area = max(max_area, isLand_bfs(grid, i, j));            
                }
            }
        }
        return max_area;
    }
    
    // dfs就是单纯的递归就好了(递归时间开销明显大)
    int isLand_dfs(vector<vector<int>>& grid, int i, int j) {
        if (i >= 0 && j >= 0 && i < grid.size() && j < grid[0].size() && grid[i][j] == 1) {
            grid[i][j] = 2;  // 直接将原始数组改变,设置为2避免了重复(包括maxAreaOfIsland函数中的重复)
            return 1 + isLand_dfs(grid, i - 1, j) + isLand_dfs(grid, i + 1, j) + isLand_dfs(grid, i, j - 1) + isLand_dfs(grid, i, j + 1);
        }
        return 0;
    }
    
    // bfs需要设置一个队列进行循环,不需要递归
    int isLand_bfs(vector<vector<int>>& grid, int i, int j) {
        int area = 0;
        queue<pair<int, int>> point;
        point.push({i, j});
        
        while (!point.empty()) {
            int x = point.front().first, y = point.front().second;
            point.pop();
            if (x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size() && grid[x][y] == 1) {
                grid[x][y] = 2;
                area++;
                point.push({x - 1, y});
                point.push({x + 1, y});
                point.push({x, y - 1});
                point.push({x, y + 1});
            }
        }
        
        return area;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.