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.
{
static HashMap<String,Integer> grps=new HashMap<String,Integer>();
static int groupsCount=0;
public static void main(String[] args)
{
System.out.println(tab[0].length+"-"+tab.length);
for(int iRow=0;iRow<tab.length;iRow++)
{
for(int iCol=0;iCol<tab[0].length;iCol++)
{
if((tab[iRow][iCol]==elementInGroup))
{
System.out.println(iRow+"-"+iCol);
getAdjacentOnes(iRow,iCol);
}
}
}
System.out.print(groupsCount+" Groups: "+grps.toString());
}
{
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);
}
}
}
Solution:
import java.util.HashMap;
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<String,Integer> grps=new HashMap<String,Integer>();
static int groupsCount=0;
public static void main(String[] args)
{
System.out.println(tab[0].length+"-"+tab.length);
for(int iRow=0;iRow<tab.length;iRow++)
{
for(int iCol=0;iCol<tab[0].length;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);
}
}
}
No comments:
Post a Comment