给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。
首先我们了解一下深度优先搜索,即从一个头结点开始,按一定的数据结构访问与头结点相连的下一个节点,再从下一个节点开始访问与当前节点相连的一个节点,循环往复,直到访问的当前节点没有下一个相连节点,开始回溯回当前节点的上一个节点,再以上一个节点为起始节点的前提下重复访问操作,不断回溯直到所有节点都被访问。
注意:访问过一个陆地节点后,一定要将访问过的节点置0,否则因为遍历地图每一块即将每一块都当做一次起始节点,会重复计算陆地面积
我们在一个土地上,以 4 个方向探索与之相连的每一个土地(以及与这些土地相连的土地),那么探索过的土地总数将是该连通形状的面积。
//遍历地图每一块 public static int maxAreaOfIsland(int[][] grid) { int area=0; //初始面积设为0 //访问每一格,以每一格都作为一次起始节点,往上下左右四个方向访问,四个方向所有连通的节点为1的总和即为该小岛屿的面积 for(int i=0;i<grid.length;i++) { for(int j=0;j<grid[0].length;j++) { area=Math.max(area, maxArea(i,j,grid)); //递归比较得到最大的岛屿面积area } } return area; } public static int maxArea(int x, int y,int[][] grid) { //确保节点合法防止数组越界且该节点为1即是陆地 if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&grid[x][y]==1) { grid[x][y]=0; //将访问过的陆地置0,防止重复访问 //返回该节点上下左右四个方向所有陆地面积 return 1+maxArea(x+1, y, grid)+maxArea(x-1, y, grid)+ maxArea(x, y-1, grid)+maxArea(x, y+1, grid); }else{ return 0; } }
广度优先搜索简单理解就是,从起始节点开始,先将与起始节点相连所有节点入队列,然后取出队首节点,将该节点相连所有未访问节点加入队尾,再取出当前队首节点,循环往复直到队列为空,即所有节点都被访问过了。
访问起始土地,并将接下来想要遍历的土地(即与起始土地四个方向相连的土地)添加到队尾,每次从队首取出土地,就实现了广度优先搜索算法。
public static int maxAreaOfIsland(int[][] grid) { int area=0; for(int i=0;i<grid.length;i++) { for(int j=0;j<grid[0].length;j++) { if(grid[i][j]==1) { area=Math.max(area, bfs(grid,i,j)); } } } return area; } public static int bfs(int grid[][],int i,int j) { Queue<int[]> queue=new LinkedList<int[]>(); //创建队列 queue.offer(new int[] {i,j}); //向队列中添加位置数组作为起始节点 grid[i][j]=0; //入队的节点(已访问)标为0 int area=1; //因为已有至少一块陆地,area初始值设为1 int[] queuei= {0,0,1,-1}; int[] queuej= {1,-1,0,0}; while(!queue.isEmpty()) { int[] tem=queue.poll(); //队首元素出队列 int x=tem[0],y=tem[1]; //起始节点位置 //把与{x,y}节点相连的所有陆地节点加入队尾 for(int k=0;k<4;k++) { int nx=x+queuei[k],ny=y+queuej[k]; if(nx>0&&nx<grid.length&&ny>0&&ny<grid[0].length&&grid[nx][ny]==1) { queue.offer(new int[] {nx,ny}); grid[nx][ny]=0; area++; } } } return area; }