计算岛屿的数量-算法题（字节笔试题，做出来了，也被撸了）

题目

有一个二维数组，其中每个元素要么是1或者0，1表示土地，连起来的1表示一个岛屿，0表示海，请计算出来二维数组用有多少个岛屿

比如：

{
  {
  1, 1, 1, 0, 1},
 {0, 1, 0, 1, 0},
 {
  1, 0, 1, 1, 1},
 {
  1, 1, 0, 1, 0}};

可以看出这二维数组中有四个岛屿

解题

通过深度优先来做，遍历过的需要做标记，碰到1开始递归标记相邻的1，碰到0就return

public class NumIslandsTest {

  public static void main(String[] args) {
    int[][] dots = {
  {1, 0, 1, 0, 1}, {0, 1, 0, 1, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 0}};
    int num = getNumIslands(dots);
    System.out.println(num);
  }

  private static int getNumIslands(int[][] dots) {
    int result = 0;
    for (int i = 0; i < dots.length; i++) {
      for (int j = 0; j < dots[i].length; j++) {
        if (dots[i][j] == 1) {
          result++;
          mark(dots, i, j);
        }
      }
    }
    return result;
  }

  private static void mark(int[][] dots, int i, int j) {
    int iMax = dots.length;
    int jMax = dots[0].length;
    if (i >= iMax || j >= jMax || i < 0 || j < 0) {
      return;
    }
    if (dots[i][j] != 1) {
      return;
    }
    dots[i][j] = 2;
    mark(dots, i - 1, j);
    mark(dots, i, j + 1);
    mark(dots, i + 1, j);
    mark(dots, i, j - 1);
  }
}