Tuesday, January 22, 2019

Program to find biggest island

package example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class IslandProblem1 {

public static void main(String[] args) {
// TODO Auto-generated method stub
   //int[][]  matrix = int[6][7];
 
   List<List<Integer>> area = new ArrayList<>();
area.add(Arrays.asList(0,0,0,1,1,0,0));
area.add(Arrays.asList(0,1, 0, 0,1,1,0));
area.add(Arrays.asList(1,1,0,1,0,0,1));
area.add(Arrays.asList(0,0,0,0,0,1,0));
area.add(Arrays.asList(1,1,0,0,0,0,0));
area.add(Arrays.asList(0,0,0,1,0,0,0));
Integer[][] areaArray = convertListToArray(area);
int size = getBiggestRegion(areaArray);
System.out.println("Biggest Island size:" +size);
}

public static int getRegionSize(Integer[][] matrix, int row, int column)
{
if(row < 0 || column < 0 || row >= matrix.length || column >= matrix[row].length)
{
return 0;
}
if(matrix[row][column] == 0)
{
return 0;
}
//System.out.println(row + " "+ column);
matrix[row][column] = 0;
int size = 1;

for(int r = row -1; r<= row+1; r++)
{
for (int c = column -1 ; c<= column+1; c++)
{
if(r != row || c!=column)
{
//System.out.println(r +" "+ c);
size += getRegionSize(matrix, r ,c);
}
}
//System.out.println("*** ");
}
return size;

}
public static int getBiggestRegion(Integer[][] matrix)
{

int maxRegion = 0;

for(int row=0; row< matrix.length; row++)
{
for(int column= 0; column <matrix[row].length; column ++)
if (matrix[row][column] == 1)
{
int size = getRegionSize(matrix, row, column);
maxRegion = Math.max(size, maxRegion);
}
}
return maxRegion;
}

static Integer[][] convertListToArray(List<List<Integer>> area) {
Integer[][] areaArray = new Integer[area.size()][];
for (int i = 0; i < area.size(); i++) {
List<Integer> list = area.get(i);
System.out.println(list);
areaArray[i] = list.toArray(new Integer[list.size()]);
}
return areaArray;
}

}

Output: 

[0, 0, 0, 1, 1, 0, 0]
[0, 1, 0, 0, 1, 1, 0]
[1, 1, 0, 1, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
Biggest Island size:7


No comments:

Post a Comment