Problem: Given a matrix with 1s and 0s, please find the number of groups of 1s. A group is defined by horizontally or vertically adjacent 1s. For example, there are four groups of 1s in Figure below which are drawn with different colors.
Solution:
import java.util.HashMap;
public class matrixGroups
{
public class matrixGroups
{
Static int[][] tab={{1,1,0,0,0}, {1,0,1,1,0}, {1,0,1,0,1}, {1,1,1,0,1}};
static int elementInGroup=1;
static HashMap grps=new HashMap();
static int groupsCount=0;
public static void main(String[] args)
{
System.out.println(tab[0].length+"-"+tab.length);
for(int iRow=0;iRow {
for(int iCol=0;iCol {
if((tab[iRow][iCol]==elementInGroup))
{
System.out.println(iRow+"-"+iCol);
getAdjacentOnes(iRow,iCol);
}
}
}
System.out.print(groupsCount+" Groups: "+grps.toString());
}
static int elementInGroup=1;
static HashMap
static int groupsCount=0;
public static void main(String[] args)
{
System.out.println(tab[0].length+"-"+tab.length);
for(int iRow=0;iRow
for(int iCol=0;iCol
if((tab[iRow][iCol]==elementInGroup))
{
System.out.println(iRow+"-"+iCol);
getAdjacentOnes(iRow,iCol);
}
}
}
System.out.print(groupsCount+" Groups: "+grps.toString());
}
//find if new group
static void getAdjacentOnes(int r,int c)
{
String current=r+"x"+c;
String top=(r-1)+"x"+c;
String left=r+"x"+(c-1);
if(r>0)//not first in rows
if(tab[r-1][c]==elementInGroup)
if(grps.containsKey(top))//group already created
grps.put(current,grps.get(top));
else //create new group
{
groupsCount++;
grps.put(top,groupsCount);
grps.put(current,groupsCount);
}
if(c>0)//not first in columns
if(tab[r][c-1]==elementInGroup)
if(grps.containsKey(left))//group already created
grps.put(current,grps.get(left));
else //create new group
{
groupsCount++;
grps.put(left,groupsCount);
grps.put(current,groupsCount);
}
}
}
static void getAdjacentOnes(int r,int c)
{
String current=r+"x"+c;
String top=(r-1)+"x"+c;
String left=r+"x"+(c-1);
if(r>0)//not first in rows
if(tab[r-1][c]==elementInGroup)
if(grps.containsKey(top))//group already created
grps.put(current,grps.get(top));
else //create new group
{
groupsCount++;
grps.put(top,groupsCount);
grps.put(current,groupsCount);
}
if(c>0)//not first in columns
if(tab[r][c-1]==elementInGroup)
if(grps.containsKey(left))//group already created
grps.put(current,grps.get(left));
else //create new group
{
groupsCount++;
grps.put(left,groupsCount);
grps.put(current,groupsCount);
}
}
}
