公司网站与营销网站在栏目上的不同,绍兴模板建站代理,怎么制作页面,网站建设图片如何加载给定一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的的二维网格#xff0c;计算岛屿的数量。一个岛被水包围#xff0c;并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010…给定一个由 1陆地和 0水组成的的二维网格计算岛屿的数量。一个岛被水包围并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000输出: 1示例 2:
输入:
11000
11000
00100
00011输出: 3
题目分析有字符‘0’代表水‘1’代表陆地岛屿指的是一个或者一片陆地相邻形成的区域所以题目要求的岛屿个数实际上求的是所有不相邻的1的个数相邻指的是上下左右。理解了题目的意思那么这一题我们很明显可以利用广度优先遍历法来实现这个问题。
代码分析我们需要定义一个数组visited来判断当前的元素是否已经被访问了如果被访问了则为true,如果没有被访问则为false. 那么我们判断当前元素是否为1如果为1则看它的相邻位置是否为‘1’一直到把所有连通域里面的‘1’访问结束后res。
class Solution {
public:int numIslands(vectorvectorchar grid) {if(grid.empty()||grid[0].empty()) return 0;int rowgrid.size();int colgrid[0].size();int res0;vectorvectorboolvisited(row,vectorbool(col,false)); //初始化visited数组为falsefor(int i0;irow;i){for(int j0;jcol;j){if(grid[i][j]1!visited){numIslandsDFS(grid,visited,i,j);res;}}}return res;
}numIslandsDFS(vectorvectorchargrid, vectorbool visited, int x,int y){if(x0||xgrid.size()) return;if(y0||ygrid[0].size()) return;if(grid[x][y]!1||visited) return;visited[x][y]true;numsIslandDFS(grid, visited,x-1,y);numsIslandDFS(grid, visited,x1,y);numsIslandDFS(grid, visited,x,y-1);numsIslandDFS(grid, visited,x,y1);
}
};
