LeetCode.200 Number of Islands

字数统计: 236阅读时长: 1 min

 2019/05/30   Share

https://leetcode.com/problems/number-of-islands/

题意

1代表陆地，0代表海水，横向纵向相连的陆地认为是同一个岛，求有几个岛
解法
开始想的是找到第一块陆地然后遍历查找，绕了一大圈发现好像不对。

正确思路就是找到第一块陆地然后向四个方向查找，并将找到的陆地置为’.’，计数加1，继续遍历直到最后一个位置

class Solution {
  public int numIslands(char[][] grid) {
      int row = grid.length;
      if (row == 0) {
          return 0;
      }
      int column = grid[0].length;
      int count = 0;
      for (int i = 0; i < row; i++) {
          for (int j = 0; j < column; j++) {
              if (grid[i][j] == '1') {
                  count++;
                  set(grid, i, j);
              }
          }
      }
      return count;
  }

  void set(char[][] grid, int i, int j) {
      int row = grid.length, column = grid[0].length;
      if (i < 0 || i >= row) {
          return;
      }
      if (j < 0 || j >= column) {
          return;
      }
      if (grid[i][j] == '1') {
          grid[i][j] = '.';
          set(grid, i + 1, j);
          set(grid, i, j + 1);
          set(grid, i - 1, j);
          set(grid, i, j - 1);
      }
  }
}

原文作者：Matteo

原文链接：http://tlzxsun.github.io/2019/05/30/LeetCode-200-Number-of-Islands/

发表日期：May 30th 2019, 9:07:56 am

更新日期：May 30th 2019, 9:07:56 am