代码随想录 695.岛屿的最大面积

思路：

1.注意题目中的每座岛屿只能由水平方向和竖直方向相邻的陆地连接形成。

2.这题也是bfs、dfs的基础题目，就是搜索每个岛屿上“1”的数量，然后取一个最大的。

一、DFS：

附代码：

class Solution { public int maxAreaOfIsland(int[][] grid) { int res = 0; for(int i = 0;i < grid.length;i++){ for(int j = 0;j < grid[i].length;j++){ if(grid[i][j] == 1){ //发现新岛屿 res = Math.max(res,dfs(grid,i,j)); //将整个岛屿标记为已访问，统计岛屿面积并求最大岛屿面积 } } } return res; } private int dfs(int[][] grid,int i,int j){ if(i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0){ return 0; } //当前节点 int count = 1; //将当前岛屿标记为已访问（沉没岛屿，改为0） grid[i][j] = 0; //向四个方向递归探索 count += dfs(grid,i - 1,j); count += dfs(grid,i + 1,j); count += dfs(grid,i,j + 1); count += dfs(grid,i,j - 1); return count; } }

二、BFS：

附代码：

class Solution { public int maxAreaOfIsland(int[][] grid) { int res = 0; for(int i = 0;i < grid.length;i++){ for(int j = 0;j < grid[0].length;j++){ if(grid[i][j] == 1){ res = Math.max(res,bfs(grid,i,j)); } } } return res; } private int bfs(int[][] grid,int i,int j){ int[] dx = {1,-1,0,0}; int[] dy = {0,0,1,-1}; LinkedList<int[]> queue = new LinkedList<>(); queue.add(new int[] {i,j}); grid[i][j] = 0; int count = 1; while(!queue.isEmpty()){ int[] cur = queue.remove(); for(int index = 0;index < 4;index++){ int nx = cur[0] + dx[index],ny = cur[1] + dy[index]; if(nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && grid[nx][ny] == 1){ grid[nx][ny] = 0; count += 1; queue.add(new int[] {nx,ny}); } } } return count; } }