LeetCode 695. 島嶼的最大面積【c++/java詳細題解】

1、題目

給定一個包含了一些 0 和 1 的非空二維陣列 grid ，

一個 島嶼 是由一些相鄰的 1 (代表土地) 構成的組合，這里的「相鄰」要求兩個 1 必須在水平或者豎直方向上相鄰，你可以假設 grid的四個邊緣都被 0（代表水）包圍著，

找到給定的二維陣列中最大的島嶼面積，(如果沒有島嶼，則回傳面積為 0 ，)

示例 1:

[[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]]

對于上面這個給定矩陣應回傳 6，注意答案不應該是 11 ，因為島嶼只能包含水平或垂直的四個方向的 1 ，

示例 2:

[[0,0,0,0,0,0,0,0]]

對于上面這個給定的矩陣, 回傳 0，

注意: 給定的矩陣grid 的長度和寬度都不超過 50，

2、思路

(DFS) O ( n ? m ) O(n*m) O(n?m)

給定一個由0和1組成的二維陣列grid，其中1代表島嶼土地，要求找出二維陣列中最大的島嶼面積，沒有則回傳0，

樣例：

如樣例所示，二維陣列grid的最大島嶼面積為4，下面來講解深度優先搜索的做法，

我們定義這樣一種搜索順序，即先搜索島嶼上的某塊土地，然后以4個方向向四周探索與之相連的每一塊土地，搜索程序中維護一個area變數，用來記錄搜索過的土地總數，為了避免重復搜索，在這個程序中需要將已經搜索過的土地置為0，最后我們回傳最大的area即可，

搜索函式設計：

int dfs(int x, int y)

x，y是當前搜索到的二維陣列grid的橫縱坐標，

實作細節：

• 1、為了確保每個位置只被搜索一次，從當前搜索過的位置繼續搜索下一個位置時，需要對當前位置進行標識，表示已經被搜索，
• 2、將二維陣列grid以及二維陣列的行數n和列數m都定義為全域變數可以減少搜索函式dfs的引數數量，
• 3、使用偏移陣列來簡化代碼，如下圖所示：

具體程序如下：

• 1、定義res = 0，遍歷grid陣列，
• 2、如果當前grid陣列元素grid[i][j] == 1，也就是說為土地的話，就以當前土地(i,j)為起點繼續向四周搜索聯通的土地，
• 3、直到搜索完當前土地的所有的連通土地，最后將連通土地總數記錄到area中，
• 4、執行res = max(res,area),不斷更新答案，

時間復雜度分析： O ( n ? m ) O(n*m) O(n?m)， n n n是二維陣列的行數， m m m是二維陣列的列數，每個位置只被搜索一次，

3、c++代碼

class Solution {
public:
    int n, m;
    vector<vector<int>>g;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //偏移陣列
    int dfs(int x, int y) //搜索函式
    {
        int area = 1;
        g[x][y] = 0;  //已經搜索過，標記為0
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            //當前土地未出界也未被搜索過，繼續下一層搜索
            if(a >=0 && a < n && b >=0 && b < m && g[a][b])
                area += dfs(a, b);
        }      
        return area; //回傳連通土地總數
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        g = grid;
        int res = 0;
        n = grid.size(), m = grid[0].size();
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(g[i][j])
                    res = max(res,dfs(i,j));
        return res;                
    }
};

4、java代碼

class Solution {
    private int n, m;
    private int[][] g;
    private int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};//偏移陣列
    public int dfs(int x, int y) //搜索函式
    {
        int area = 1;
        g[x][y] = 0; //已經搜索過，標記為0
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            //當前土地未出界也未被搜索過，繼續下一層搜索
            if(a >=0 && a < n && b >= 0 && b < m && g[a][b] != 0)
                area += dfs(a, b);
        }      
        return area; //回傳連通土地總數
    }
    public int maxAreaOfIsland(int[][] grid) {
        g = grid;
        int res = 0;
        n = grid.length; m = grid[0].length;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(g[i][j] != 0)
                    res = Math.max(res,dfs(i,j));
        return res;  
    }
}

原題鏈接： 695. 島嶼的最大面積