LeetCode 695：岛屿的最大面积

题目描述

标准解法：DFS $O(n*m)$

基本思想比较简单，就是dfs走遍整个地图，记录最大的面积，走过的地标为0下次不再走。题解的代码很简洁，可以参考。

class Solution {
    int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
        if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1)
            return 0;
        grid[cur_i][cur_j] = 0;
        int di[4] = {0, 0, 1, -1};
        int dj[4] = {1, -1, 0, 0};
        int ans = 1;
        for (int index = 0; index != 4; ++index) {
            int next_i = cur_i + di[index], next_j = cur_j + dj[index];
            ans += dfs(grid, next_i, next_j);
        }
        return ans;
    }
public:
    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;
    }
};

个人解法 DFS菜鸡版 $O(n*m)$

我的代码就很丑，但是比较容易理解。用vis记录一块地有没有走过，go函数执行dfs的功能，上下左右走的每一步也很清晰。

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();

        // cout << n << " " << m << endl;

        if (n == 0) {
            return 0;
        }

        vector<vector<bool>> vis;
        for (int i = 0; i < n; i++) {
            vector<bool> col;
            for (int j = 0; j < m; j++) {
                col.push_back(false);
            }
            vis.push_back(col);
        }
        
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j]) {
                    int tmp = go(i, j, n, m, vis, grid);
                    if (tmp > max) {
                        max = tmp;
                    }
                }
            }
        }

        return max;
    }

    int go(int i, int j, const int& n, const int& m, vector<vector<bool>>& vis, vector<vector<int>>& grid) {
        

        vis[i][j] = true;

        int area = 0;

        if (grid[i][j]) {
            
            area = 1;
            // up
            if (i - 1 >= 0 && !vis[i-1][j]) {
                area += go(i-1, j, n, m, vis, grid);
            }
            // down
            if (i + 1 < n && !vis[i+1][j]) {
                area += go(i+1, j, n, m, vis, grid);
            }
            // left
            if (j - 1 >= 0 && !vis[i][j-1]) {
                area += go(i, j-1, n, m, vis, grid);
            }
            // right
            if (j + 1 < m && !vis[i][j+1]) {
                area += go(i, j+1, n, m, vis, grid);
            }
        }

        return area;
    }
};

总结

题解中将1置0从而省去vis数组，很好地降低了空间开销，也省去了初始化。

此外，max函数为什么不用！！！

参考

官方题解