AC bfs solution -- Java


  • 0
    H
    public class Solution {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) return 0;
            int count = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] == '1') {
                        bfsHelper(grid, i, j);
                        count++;
                    }
                }
            }
            return count;
        }
        private void bfsHelper(char[][] grid, int i, int j) {
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{i, j});
            int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
            while(!queue.isEmpty()) {
                //poll out e in queue, and offer its neighbor
                int [] idx = queue.poll();
                for (int k = 0; k < dirs.length; k++) {
                    int x = idx[0] + dirs[k][0];
                    int y = idx[1] + dirs[k][1];
                    if (isBound(grid, x, y)) {
                        //is island and not water !
                        if (grid[x][y] == '0') {
                            continue;
                        }
                        //not visited
                        if (grid[x][y] != 'X') {
                           queue.offer(new int[]{x, y});  
                           //mark as visited
                           grid[x][y] = 'X';
                        } 
                    }
                }
            }
            return;
        }
        private boolean isBound(char[][] grid, int i, int j) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
                return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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