695. Max Area of Island

Question

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.

Solution

DFS搜索, 维护一个变量count，为连续执行DFS搜索的次数。
遍历地图上所有为1的位置。

运行BFS时每次将全局变量count增加1。
执行完毕后BFS时将全局变量count清零。

遍历每个等于1的地图块。
递归周围四个地图块，当超越数组范围，或者当前位置不为1时返回。
进行搜索时将搜索过的地图块标记为0，不再重复搜索。

Code

class Solution {
    int[][] visited, directions;
    int count;
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int x = 0; x < grid.length; x++){
            for(int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 1){
                    count = 0;
                    dfs(grid, x, y);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
    
    private void dfs(int[][] grid, int x, int y){
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return;
        grid[x][y] = 0;
        count++;
        for(int[] direction : directions){
            int i = x + direction[0];
            int j = y + direction[1];
            dfs(grid, i, j);
        }
    }
}