695. Max Area of Island - Medium

前往題目

想法

• 和之前寫過的島嶼類似，但忘了怎麼開頭，只知道DFS會輕鬆一些

思路

1. 利用DFS
2. 從第一個cell開始，遇到水就跳過，遇到走過的cell也跳過，出界的也跳過
3. 把每個區域的1都走過然後加起來，因為dfs遇到出界或是海水就會回傳，所以最終每個區域的面積都可以被單獨算出來，因為演算法不會越過水到另一片陸地。

Code

class Solution {
    private int ROWS;
    private int COLS;

    public int maxAreaOfIsland(int[][] grid) {
        ROWS = grid.length;
        COLS = grid[0].length;

        int res = 0;

        // Check every cell
        for (int row = 0; row < ROWS; ++row) {
            for (int col = 0; col < COLS; ++col) {
                // Record the maximum
                res = Math.max(res, dfs(grid, row, col));
            }
        }

        return res;
    }

    private int dfs(int[][] grid, int row, int col) {
        // Check visited, inBound, and water
        // 這個return可以防止越過水到另一片陸地
        if (!isInBound(row, col) || grid[row][col] == 0) {
            return 0;
        }

        // Change to water indicates visited
        grid[row][col] = 0;

        // Sum up all the area including the current cell
        return 1 + dfs(grid, row + 1, col) + 
                    dfs(grid, row - 1, col) + 
                    dfs(grid, row, col + 1) +
                    dfs(grid, row, col - 1);
    }

    private boolean isInBound(int row, int col) {
        return row >= 0 && row < ROWS && col >= 0 && col < COLS;
    }
}