首页 > 代码库 > 百度真题之城市规划（连通域数目）
百度真题之城市规划（连通域数目）
题目：
给出一个二维矩阵，矩阵元素为1或0，计算由1构成的独立不连通的区域数目，斜角为1也算连通。如以下矩阵：
0 1 0 0 0 0
0 1 0 1 0 0
0 0 0 0 1 1
连通域的个数为2.
分析：
建立一个集合list保存已经标记的坐标，循环遍历每一个点，当该点的值为1并且未被标记的话，将该点标记，并标记与该点相邻的点（使用递归，可以标记与该点连通的所有点）。
以下代码：
package project001;import java.util.ArrayList;import java.util.List;public class Main09 {//找到矩阵中1的非连通区域的个数，斜对角也算连通 public static List<int[]> markedList = new ArrayList<int[]>(); public static void main(String[] args) { int[][] maze = {{0,0,0,0,0}, {0,1,0,0,0}, {0,0,0,1,0}, {1,1,0,0,0}, {0,0,0,1,1}}; double t = System.currentTimeMillis(); System.out.println(getL(fillM(maze))); } public static int getL(int[][] M){ int count = 0; int row = M.length; int col = M[0].length; for(int i = 0;i<row;i++){ for(int j=0;j<col;j++){ //当该点为被标记，并且为1时，标记所有与该点连通的点 if(M[i][j]==1 && !isMarked(i,j)){ markPoint(i,j,M); count++; } } } return count; } public static int[][] fillM(int[][] M){ int row = M.length; int col = M[0].length; int[][] M2 = new int[row+2][col+2]; for(int i = 1;i<=row;i++){ for(int j=1;j<=col;j++){ M2[i][j]=M[i-1][j-1]; } } return M2; } //判断该点是否被标记 public static boolean isMarked(int i,int j){ int size = markedList.size(); if(size<=0) return false; for(int k=0;k<size;k++){ int[] m = markedList.get(k); if(m[0]==i&&m[1]==j) return true; } return false; } //标记点（i,j）并且标记所有与该点连通的区域 public static void markPoint(int i,int j,int[][] M){ if(isMarked(i,j)) return ; //将该点标记，即放入一个list内 int[] m = new int[]{i,j}; markedList.add(m); //标记与点(i,j)相邻并且未被标记的点 if(!isMarked(i-1,j-1)&&M[i-1][j-1]==1) markPoint(i-1,j-1,M); if(!isMarked(i-1,j)&&M[i-1][j]==1) markPoint(i-1,j,M); if(!isMarked(i-1,j+1)&&M[i-1][j+1]==1) markPoint(i-1,j+1,M); if(!isMarked(i,j-1)&&M[i][j-1]==1) markPoint(i,j-1,M); if(!isMarked(i,j+1)&&M[i][j+1]==1) markPoint(i,j+1,M); if(!isMarked(i+1,j-1)&&M[i+1][j-1]==1) markPoint(i+1,j-1,M); if(!isMarked(i+1,j)&&M[i+1][j]==1) markPoint(i+1,j,M); if(!isMarked(i+1,j+1)&&M[i+1][j+1]==1) markPoint(i+1,j+1,M); } //打印矩阵 public static void printM(int[][] m){ int row = m.length; int col = m[0].length; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ System.out.print(m[i][j]+" "); } System.out.println(""); } }}
百度真题之城市规划（连通域数目）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。