矩阵中1的组/岛数：定义说明

本文介绍了矩阵中1的组/岛数：定义说明的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在研究矩阵中1的组（或岛）数的各种解决方案，同时以下内容清晰&简洁的Java解决方案朝着正确的方向发展，但对我来说也不完整：

I am studying various solutions for Number of Groups (or "islands") of 1's in a Matrix, and while the following clear & concise Java solution looks in the right direction, it also looks incomplete to me:

/* * Given a matrix of 0's and 1's, * find the number of groups of 1's in the matrix. * * A group of 1's is defined as all ADJACENT 1's * vertically or horizontally but not diagonally. */ public class Islands { /** * main entry point */ public static void main(String[] args) { int[][] A = new int[4][4]; int totalNumGroups = 0; int curCnt = 0; /* * Initialize 2-dimensional array with 1's and 0's (randomly!) * For testing/verification purpose only */ for(int x=0; x<A.length; x++) { for(int y=0; y<A[x].length; y++) { A[x][y] = (int) Math.round(Math.random()); System.out.print(A[x][y] + " "); } System.out.println(" "); } /* * The crux of the solution: iterate through all (x,y): * If encountered a 1, * reset current count and * increase total number of groups by what clean_block returns. */ for(int x=0; x<A.length; x++) { for(int y=0; y<A[x].length; y++) { if (A[x][y] == 1) { curCnt = 0; totalNumGroups = totalNumGroups + cleanBlock(A, x,y, curCnt); } // else (0), keep curCnt and totalNumGroups as are. } } System.out.println("\nTotal # of groups: " + totalNumGroups); } /* * Recursively clean found 1 and its adjacent 1's. */ public static int cleanBlock(int[][] A, int x, int y, int cnt) { A[x][y] = 0; if (inMatrix(x-1,y ,A.length,A[0].length) == 1 && A[x-1][y] == 1) { cleanBlock(A, x-1,y ,cnt); cnt = 1; } if (inMatrix(x+1,y ,A.length,A[0].length) == 1 && A[x+1][y] == 1) { cleanBlock(A, x+1,y ,cnt); cnt = 1; } if (inMatrix(x,y-1 ,A.length,A[0].length) == 1 && A[x][y-1] == 1) { cleanBlock(A, x,y-1 ,cnt); cnt = 1; } if (inMatrix(x,y+1 ,A.length,A[0].length) == 1 && A[x][y+1] == 1) { cleanBlock(A, x,y+1 ,cnt); cnt = 1; } return cnt; } public static int inMatrix(int x, int y, int lenX, int lenY) { if ( (x >= 0 && x <= (lenX-1)) && (y >= 0 && y <= (lenY-1)) ) return 1; else return 0; } }

这是因为它不计算单个1（以0包围）。例如此4x4矩阵的输出仅产生单个组：

That is because it does not count a single 1 (surrounded by 0's) as a group. e.g. the output for this 4x4 matrix yields a single group only:

1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 Total # of groups: 1

所以，我的问题是：被0包围的单个1是否被视为一个组？

So, my question is: Is a single 1 surrounded by 0's considered a group?

推荐答案

正确是因为根据问题：

如果垂直出现$ 1或水平出现，则可以形成一组1相邻的1

A group of 1's can be formed if a 1 is present either vertically or horizontally to the adjacent 1

因此，在您的情况下，不能将一个孤独的1计为一个组，因为在水平方向上没有其他1或垂直。

So in your case, a lonely 1 can't be counted as a group because there's no other 1 adjacent horizontally or vertically.