电商直播_工程建设游戏_牛推网_网络营销策略的定义

解法一：深度优先搜索

• 我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
• 为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
• 最终岛屿的数量就是我们进行深度优先搜索的次数。

class Solution {public int numIslands(char[][] grid) {if(grid==null || grid.length==0){return 0;}int n = grid.length;int m = grid[0].length;int sum = 0;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(grid[i][j]=='1'){sum++;dfs(grid, i, j);}}}return sum;}public void dfs(char[][] grid, int i, int j){int n = grid.length;int m = grid[0].length;if(i<0 || j<0 || i>=n || j>=m || grid[i][j]=='0'){return;}// 重置+遍历grid[i][j]='0';  //grid[i][j]=0;dfs(grid, i-1, j);dfs(grid, i+1, j);dfs(grid, i, j-1);dfs(grid, i, j+1);}
}

注意：

• 这里的数组是char数组，要用‘0’和‘1’来判断，而不是0和1。例如：grid[i][j]=0 => × grid[i][j]='0' => √