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;
}
}
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