矩阵中1的组/岛数:定义说明 [英] Number of Groups/Islands of 1's in a Matrix: Definition clarification
问题描述
我正在研究矩阵中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.
这篇关于矩阵中1的组/岛数:定义说明的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!