岛屿的个数

这题考察广度优先遍历和深度优先遍历，利用递归的方式做还算比较简单，但是输出的格式有待斟酌！

几个岛（滴滴）

题目：

给定一个m行n列的二维地图, 初始化每个单元都是水.
操作addLand 把单元格(row,col)变成陆地.
岛屿定义为一系列相连的被水单元包围的陆地单元, 横向或纵向相邻的陆地称为相连(斜对角不算).
在一系列addLand的操作过程中, 给出每次addLand操作后岛屿的个数.
二维地图的每条边界外侧假定都是水.

输入示例：

输入：
3
3
4
0 0
0 1
1 2
2 1

输出示例：

1 1 2 3

解题思想：

• 这类可以可以将转换为一个二维数组中连续1的个数问题（陆地为1，水为0）。即： image.png
• 在任意一节点利用DFS递归的找出这个节点的上下左右的节点是否为1。

package com.zhoujian.solutions.didi;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author zhoujian123@hotmail.com 2018/8/26 17:07
 */
public class Island {

    static int m;
    static int n;
    static int k;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        int k = sc.nextInt();
        int[][] nums = new int[m][n];
        for (int i = 0; i < k; i++) {
            int i1 = sc.nextInt();
            int i2 = sc.nextInt();
            nums[i1][i2] = 1;
        }
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                System.out.println(nums[i][j]);
//            }
//        }
        LinkedList<Integer> linkedList = findIsland(nums, m, n);
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
    }

    private static LinkedList<Integer> findIsland(int[][] nums, int m, int n) {
        int count = 0;
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (nums[i][j] == 1) {
                    DFSMarking(nums, i, j);
                    ++count;
                    list.add(count);
                }
            }
        }
        return list;
    }

    private static void DFSMarking(int[][] nums, int i, int j) {
        if (i < 0 || j < 0 || i >= n || j >= m || nums[i][j] != 1) {
            return;
        }
        nums[i][j] = 0;
        DFSMarking(nums, i + 1, j);
        DFSMarking(nums, i - 1, j);
        DFSMarking(nums, i, j + 1);
        DFSMarking(nums, i, j - 1);
    }
}

输出如下：

image.png

相关题目：

200岛屿的个数（LeetCode）

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。