LeetCode 200. Number of Islands

Question

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Answer: 1

Example 2:

Answer: 3

Explanation

运用BFS，找到一个1以后把周围的1标为‘0’。从而确定island的个数。

Code

public class Solution {
    //create a class as one point
    class Coordinate{
        int x, y;
        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int n = grid.length;
        int m = grid[0].length;
        int islands = 0;
        //find island from every '1'
        for (int i=0; i<n; i++) {
            for (int j =0; j < m; j++) {
                if (grid[i][j] == '1') {
                    markByBFS(grid, i, j);
                    islands++;
                }
            }
        }
        return islands;
    }
    //mark the island around '1' as '0' to avoid duplications
    private void markByBFS(char[][] grid,int x, int y) {
        //four directions, up, left, right, down
        int[] directorX = {0, 1, -1, 0};
        int[] directorY = {1, 0, 0, -1};
        //using queue, BFS
        Queue<Coordinate> queue = new LinkedList<>();
        queue.offer(new Coordinate(x,y));
        grid[x][y] = '0';
        while(!queue.isEmpty()) {
            Coordinate coor = queue.poll();
            for(int i=0; i<4; i++) {
                Coordinate adj = new Coordinate(
                    coor.x + directorX[i],
                    coor.y + directorY[i]
                    );
                //avoid for invalid point
                if ( !inBound(adj, grid)) {
                    continue;
                }
                if (grid[adj.x][adj.y] == '1') {
                    grid[adj.x][adj.y] = '0';
                    queue.offer(adj);
                }
            }
        }
    }
    private boolean inBound(Coordinate adj,char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        return adj.x >=0 && adj.x <n &&adj.y >=0 && adj.y<m;
    }
}