LeetCode热题100 岛屿数量

题目描述给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。示例 1输入grid [[‘1’,‘1’,‘1’,‘1’,‘0’],[‘1’,‘1’,‘0’,‘1’,‘0’],[‘1’,‘1’,‘0’,‘0’,‘0’],[‘0’,‘0’,‘0’,‘0’,‘0’]]输出1示例 2输入grid [[‘1’,‘1’,‘0’,‘0’,‘0’],[‘1’,‘1’,‘0’,‘0’,‘0’],[‘0’,‘0’,‘1’,‘0’,‘0’],[‘0’,‘0’,‘0’,‘1’,‘1’]]输出3提示m grid.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 ‘0’ 或 ‘1’思路对陆地进行深度优先搜索将搜索到的陆地标记为水每搜索一次就是一个岛屿。代码classSolution{public:intdx[4]{1,-1,0,0},dy[4]{0,0,1,-1};intnumIslands(vectorvectorchargrid){intngrid.size(),mgrid[0].size();intans0;for(inti0;in;i){for(intj0;jm;j){if(grid[i][j]1){dfs(grid,i,j,n,m);ans;}}}returnans;}voiddfs(vectorvectorchargrid,intx,inty,intn,intm){grid[x][y]0;for(inti0;i4;i){intxxxdx[i],yyydy[i];if(xx0xxnyy0yymgrid[xx][yy]1){dfs(grid,xx,yy,n,m);}}}};