首页

# 深度优先搜索

class Solution {
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};
public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        int lenx = grid.size(), leny = grid[0].size();
        int curArea = 0;
        for (int x = 0; x < grid.size(); x++) {
            for (int y = 0; y < grid[0].size(); y++) {
                if (grid[x][y]) {
                    curArea = max(dfs(grid, x, y), curArea);
                }
            }
        }
        return curArea;
    };
    // 返回的是面积
    int dfs(vector<vector<int>> &grid, int x, int y) {
        if (grid[x][y] == 0) {
            return 0;
        }
        // 计算过这里的面积了，置为 0，这样之后不会进入
        grid[x][y] = 0;
        int area = 1;
        for (int i = 0; i < dx.size(); i++) {
            int x2 = x + dx[i], y2 = y + dy[i];
            if (x2 >= 0 && x2 < grid.size() && y2 >= 0 && y2 < grid[0].size()) {
                area += dfs(grid, x2, y2);
            }
        }
        return area;
    }
};