My BFS solution in Java


  • 1
    S
    public int maxAreaOfIsland(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(!visited[i][j] && grid[i][j] == 1) res = Math.max(res, bfs(grid, visited, i, j));
            }
        }
        return res;
    }
    
    int[][] moves = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private int bfs(int[][] grid, boolean[][] visited, int row, int col) {
        Queue<int[]> q = new LinkedList<>();
        int res = 1;
        q.add(new int[]{row, col});
        visited[row][col] = true;
        while(!q.isEmpty()) {
            int[] curCoor = q.poll();
            for(int[] move : moves) {
                int i = curCoor[0] + move[0];
                int j = curCoor[1] + move[1];
                if(isLegal(grid, i, j) && grid[i][j] == 1 && !visited[i][j]) {
                    visited[i][j] = true;
                    res++;
                    q.add(new int[]{i, j});
                }
            }
        }
        return res;
    }
    private boolean isLegal(int[][] grid, int row ,int col) {
        return row >= 0 && row < grid.length && col >= 0 && col < grid[row].length;
    }
    

  • 0
    O

    Same idea but i didn't have time to refactor the code.

    class Solution(object):
        def maxAreaOfIsland(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            helper = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
            maxArea = 0
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    area = 0
                    queue = []
                    if grid[i][j] and not helper[i][j]:
                        helper[i][j] = True
                        queue.append((i, j))
                    while queue:
                        n = len(queue)
                        area += n
                        while n:
                            tmp_i, tmp_j = queue.pop(0)
                            n -= 1
                            if tmp_i-1 >= 0 and grid[tmp_i-1][tmp_j] and not helper[tmp_i-1][tmp_j]:
                                helper[tmp_i - 1][tmp_j] = True
                                queue.append((tmp_i - 1, tmp_j))
    
                            if tmp_i+1 < len(grid) and grid[tmp_i+1][tmp_j] and not helper[tmp_i+1][tmp_j]:
                                helper[tmp_i + 1][tmp_j] = True
                                queue.append((tmp_i + 1, tmp_j))
    
                            if tmp_j-1 >= 0 and grid[tmp_i][tmp_j-1] and not helper[tmp_i][tmp_j-1]:
                                helper[tmp_i][tmp_j-1] = True
                                queue.append((tmp_i, tmp_j-1))
    
                            if tmp_j+1 < len(grid[0]) and grid[tmp_i][tmp_j+1] and not helper[tmp_i][tmp_j+1]:
                                helper[tmp_i][tmp_j+1] = True
                                queue.append((tmp_i, tmp_j+1))
    
                    maxArea = max(area, maxArea)
    
            return maxArea
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.