LeetCode-695. Max Area of Island [C++][Java]

LeetCode-695. Max Area of Islandhttps://leetcode.com/problems/max-area-of-island/

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

m == grid.lengthn == grid[i].length1 <= m, n <= 50grid[i][j] is either 0 or 1.

class Solution {
public:
    int maxAreaOfIsland(vector>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0, local_area, area = 0, x, y;
        vector direction{-1, 0, 1, 0, -1};
        for (int i=0; i> island;
                    island.push({i, j});
                    while (!island.empty()) {
                        auto [r, c] = island.top(); island.pop();
                        for (int k=0; k<4; ++k) {
                            x = r + direction[k], y = c + direction[k+1];
                            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
                                grid[x][y] = 0;
                                ++local_area;
                                island.push({x, y});
                            }
                        }
                    }
                    area = max(area, local_area);
                }
            }
        }
        return area;
    }
};

class Solution {
public:
    int maxAreaOfIsland(vector>& grid) {
        int result = 0, m = grid.size(), n = grid[0].size();
        Utils utils;
        for(int i=0; i> &grid, int x, int y, int m, int n) {
                if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {return 0;}
                int count = 1;
                grid[x][y] = 0;//注意，在递归前需要先把当前格子更新为0
                for (auto &step : steps) {count += dfs(grid, x+step[0], y+step[1], m, n);}
                return count;
            }
    };
};

class Solution {
public:
    int steps[4][2] = {{-1, 0}, {1,  0}, {0,  -1}, {0,  1}};
    inline bool IsInGrid(const vector> &grid, int i, int j) {
        return i >= 0 && j >= 0 && i < grid.size() && j < grid[i].size();
    }

    void FindAreaOfIsland(vector> &grid, int i, int j, int &area) {
        if (!grid[i][j]) {return;}
        grid[i][j] = 0;
        area++;
        for (int k = 0; k < 4; ++k) {
            int new_i = i + steps[k][0];
            int new_j = j + steps[k][1];
            if (!IsInGrid(grid, new_i, new_j) || !grid[new_i][new_j]) {continue;}
            FindAreaOfIsland(grid, new_i, new_j, area);
        }
        return ;
    }

    int maxAreaOfIsland(vector>& grid) {
        int max_area = 0, area;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (!grid[i][j]) continue ;
                area = 0;
                FindAreaOfIsland(grid, i, j, area);
                if (area > max_area) max_area = area;
            }
        }
        return max_area;
    }
};

整理一下

class Solution {
    vector direction{-1, 0, 1, 0, -1};
public:
    int maxAreaOfIsland(vector>& grid) {
        if (grid.empty() || grid[0].empty()) {return 0;}
        int max_area = 0;
        for (int i=0; i>& grid, int r, int c) {
        if (grid[r][c] == 0) {return 0;}
        grid[r][c] = 0;
        int x, y, area = 1;
        for (int i=0; i<4; i++) {
            x = r + direction[i], y = c + direction[i+1];
            if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size()) {
                area += dfs(grid, x, y);
            }
        }
        return area;
    }
};

再换种思路

class Solution {
public:
    int maxAreaOfIsland(vector>& grid) {
        if (grid.empty() || grid[0].empty()) {return 0;}
        int max_area = 0;
        for (int i=0; i>& grid, int r, int c) {
        if (r < 0 || r >= grid.size()
            || c < 0 || c >= grid[0].size() || grid[r][c] == 0) {return 0;}
        grid[r][c] = 0;
        return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c)
                 + dfs(grid, r, c + 1) + dfs(grid, r, c - 1);
    }
};

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {return 0;}
        int max_area = 0;
        for (int i=0; i= grid.length
           || c < 0 || c >= grid[0].length || grid[r][c] == 0) {return 0;}
        grid[r][c] = 0;
        return 1 + dfs(grid, r + 1, c) + dfs(grid, r - 1, c)
                 + dfs(grid, r, c + 1) + dfs(grid, r, c - 1);
    }
}