LintCode 433 Number of Islands

思路

BFS， 从全图中所有为1的地方开始BFS，向4个方向进行搜索，在将起点加入queue的同时将其标记为0或者开一个visit数组标记已访问。

复杂度

• 时间复杂度O(n*m）
• 空间复杂度O(n*m)

代码

class Coordinate {
    int x, y;public Coordinate(int x, int y) {
    this.x = x;this.y = y;}
}
public class Solution {
    /*** @param grid: a boolean 2D matrix* @return: an integer*/public int numIslands(boolean[][] grid) {
    // write your code hereif (grid.length == 0 || grid[0].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] == true) {
    bfs(grid, i, j);count++;}}}return count;}private void bfs(boolean[][] grid, int x, int y) {
    int[] dx = {
    -1, 1, 0, 0};int[] dy = {
    0, 0, -1, 1};Queue<Coordinate> queue = new LinkedList<>();queue.offer(new Coordinate(x, y));grid[x][y] = false;while (!queue.isEmpty()) {
    Coordinate coor = queue.poll();for (int i = 0; i < 4; i++) {
    Coordinate next = new Coordinate(coor.x + dx[i],coor.y + dy[i]);if (!inBound(next, grid)) {
    continue;}if (grid[next.x][next.y]) {
    queue.offer(next);grid[next.x][next.y] = false;}}}}private boolean inBound(Coordinate coor, boolean[][] grid) {
    return 0 <= coor.x && coor.x < grid.length && 0 <= coor.y && coor.y < grid[0].length; }
}