Find largest island in a board
1 package fb; 2 3 public class LargestIsland { 4 public int findLargestIsland(int[][] board) { 5 if (board==null || board.length==0 || board[0].length==0) return 0; 6 int m = board.length; 7 int n = board[0].length; 8 int maxArea = 0; 9 for (int i=0; i<m; i++) { 10 for (int j=0; j<n; j++) { 11 if (board[i][j] != 1) continue; 12 int area = 0; 13 area = dfs(board, i, j, m, n); 14 maxArea = Math.max(maxArea, area); 15 } 16 } 17 return maxArea; 18 } 19 20 21 public int dfs(int[][] board, int i, int j, int m, int n) { 22 if (i<0 || i>=m || j<0 || j>=n || board[i][j]!=1) return 0; 23 int area = 1; 24 board[i][j] = 2; 25 area += dfs(board, i-1, j, m, n); 26 area += dfs(board, i+1, j, m, n); 27 area += dfs(board, i, j-1, m, n); 28 area += dfs(board, i, j+1, m, n); 29 return area; 30 } 31 32 /** 33 * @param args 34 */ 35 public static void main(String[] args) { 36 // TODO Auto-generated method stub 37 LargestIsland sol = new LargestIsland(); 38 //int[][] arr = new int[][]{{1,0,0,0},{0,1,0,0},{0,0,1,1},{0,0,1,1}}; 39 int[][] arr = new int[][]{{1,0,1},{0,1,0},{0,1,1}}; 40 int res = sol.findLargestIsland(arr); 41 System.out.println(res); 42 } 43 44 }