美文网首页
岛屿个数

岛屿个数

作者: no_one11 | 来源:发表于2017-09-23 22:04 被阅读0次

题目
给定一个m行n列的二维地图,初始化每个单元都是水,操作addLand把单元格(row,col)变成陆地。岛屿定义为一系列想连的被水单元包围的陆地单元,横向和纵向相邻的陆地称为相连(斜对角不算)。在一系列addLand的操作过程中,给出每次addLand的操作后的岛屿的个数。二维地图的每条边外侧假定都是水。
样列
输入 (行,列,addLand操作次数,addLand每次操作的坐标)
3
3
4
0 0
0 1
1 2
2 1
输出(每次addLand后岛屿的个数)
1 1 2 3

代码

import java.util.Scanner;

public class Main1 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        int n = scan.nextInt();
        int num = scan.nextInt();
        int[][] nums = new int[num][2];
        for(int i=0;i<num;i++){
            nums[i][0] =  scan.nextInt();
            nums[i][1] =  scan.nextInt(); 
                    
        }
        int[][] ceils = new int[m+2][n+2];
        for(int i=0;i<n+2;i++){
            // 初始化第一行
            ceils[0][i] = 0;
            // 初始化最后一行
            ceils[n+1][i] = 0;
        }
        for(int i=0;i<m+2;i++){
            // 初始化第一列
            ceils[i][0] = 0;
            // 初始化最后一列
            ceils[i][m+1] = 0;
        }
        int[] result = new int[num];
        for(int i=0;i<num;i++){
            if(nums[i][0]<0 || nums[i][0]>m || nums[i][1]<0 || nums[i][1]>n){
                continue;
            }
            int row = nums[i][0]+1;
            int col = nums[i][1]+1;
            ceils[row][col] = 1;
            if(ceils[row-1][col] == 0 && 
                    ceils[row+1][col] == 0 &&
                    ceils[row][col-1] == 0 && 
                    ceils[row][col+1] == 0){
                if(i==0){
                    result[i] = 1;
                    continue;
                } 
                result[i] = result[i-1]+1;
            } else {
                result[i] = result[i-1];
            }
        }
        
        for(int i=0;i<num;i++){
            if(i==0){
                System.out.print(result[i]);
                continue;
            } 
            System.out.print(" " + result[i]);
            
        }

    }

}

相关文章

  • 岛屿个数

    题目给定一个m行n列的二维地图,初始化每个单元都是水,操作addLand把单元格(row,col)变成陆地。岛屿定...

  • 岛屿的个数

    给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或...

  • 岛屿的个数

    给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或...

  • 岛屿的个数

    这题考察广度优先遍历和深度优先遍历,利用递归的方式做还算比较简单,但是输出的格式有待斟酌! 几个岛(滴滴) 题目:...

  • 岛屿的个数

    题目 思路:搜索到陆地(1)以后向前后以及下方遍历直至搜到海(0),将搜索到的陆地全部置为0并且将岛屿数量+1。

  • LeetCode:岛屿的个数

    岛屿的个数 题目叙述: 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围...

  • 11 - Medium - 岛屿的个数

    给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或...

  • 200. 岛屿的个数

    题目描述 给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过...

  • 433. 岛屿的个数

    给一个01矩阵,求不同的岛屿的个数。0代表海,1代表岛,如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左...

  • LeetCode 岛屿个数问题求解

    I found myself not as enthusiastic as before. 这里使用岛屿下沉的思路...

网友评论

      本文标题:岛屿个数

      本文链接:https://www.haomeiwen.com/subject/atdhextx.html