[LintCode] Number of Islands(岛屿个数)

描述

给一个01矩阵,求不同的岛屿的个数。

0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

样例

在矩阵:

[
  [1, 1, 0, 0, 0],
  [0, 1, 0, 0, 1],
  [0, 0, 0, 1, 1],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1]
]

中有 3 个岛。

 

package com.ossez.lang.tutorial.tests.lintcode;

import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * <p>
 * 433
 * <ul>
 * <li>@see <a href=
 * "https://www.cwiki.us/display/ITCLASSIFICATION/Number+of+Islands">https://www.cwiki.us/display/ITCLASSIFICATION/Number+of+Islands</a>
 * <li>@see<a href="https://www.lintcode.com/problem/number-of-islands/">https://www.lintcode.com/problem/number-of-islands/</a>
 * </ul>
 * </p>
 * 
 * @author YuCheng
 *
 */
public class LintCode0433NumIslandsTest {

  private final static Logger logger = LoggerFactory.getLogger(LintCode0433NumIslandsTest.class);

  /**
   * 
   */
  @Test
  public void testMain() {
    logger.debug("BEGIN");
    // INIT GRID
    boolean[][] grid = { { true, true, false, false, false }, { false, true, false, false, true }, { false, false, false, true, true },
        { false, false, false, false, false }, { false, false, false, false, true }

    };

    // NULL CHECK
    if (grid.length == 0 || grid[0].length == 0) {
      System.out.println("NULL");
      // return 0;
    }

    // GET SIZE
    int n = grid.length;
    int m = grid[0].length;

    // ARRAY FOR VISITED LOG
    boolean[][] visited = new boolean[n][m];

    int count = 0;

    // LOOP FOR GRID
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (grid[i][j] && !visited[i][j]) {
          numIslandsDFS(grid, visited, i, j);
          count++;
        }
      }
    }

    System.out.println(count);

  }

  /**
   * 
   * @param grid
   * @param visited
   * @param x
   * @param y
   */
  public void numIslandsDFS(boolean[][] grid, boolean[][] visited, int x, int y) {
    if (x < 0 || x >= grid.length) {
      return;
    }

    if (y < 0 || y >= grid[0].length) {
      return;
    }

    if (grid[x][y] != true || visited[x][y]) {
      return;
    }

    visited[x][y] = true;

    // Recursive call
    numIslandsDFS(grid, visited, x - 1, y);
    numIslandsDFS(grid, visited, x + 1, y);
    numIslandsDFS(grid, visited, x, y - 1);
    numIslandsDFS(grid, visited, x, y + 1);

  }
}

 

点评

本质是求矩阵中连续区域的个数,很容易想到需要用深度优先搜索 DFS 来解,我们需要建立一个 visited 数组用来记录某个位置是否被访问过,对于一个为 true 且未被访问过的位置,我们递归进入其上下左右位置上为 true 的数,将其 visited 对应值赋为 true,继续进入其所有相连的邻位置,这样可以将这个连通区域所有的数找出来,并将其对应的 visited 中的值赋 true,找完次区域后,我们将结果 res 自增 1,然后我们在继续找下一个为 true 且未被访问过的位置,以此类推直至遍历完整个原数组即可得到最终结果。

这里需要有一个递归的调用。在递归调用之前需要进行判断是否超出边际,如果超出边际的话,就要跳出循环。

在一个节点进行遍历的时候,需要在递归调用的时候,同时针对这个节点搜索上下左右 4 个节点,如果找到需要了满足条件的 true,就继续查找,如果没有找到就退出。在这个过程的时候,需要将访问过的节点保存到访问控制的 2 维数组中。以便于在下次查找的时候跳过这个节点。

https://www.cwiki.us/display/ITCLASSIFICATION/Number+of+Islands

您可以在保留原文链接的情况下转载:HoneyMoose » [LintCode] Number of Islands(岛屿个数)

赞 (0) 打赏

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏