200.岛屿数量给你一个由 ‘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【思路】递归思想先遍历网格若元素为’1’则可以以此点展开dfs操作dfs操作深度优先搜索过程中将搜索到的’1’都写为‘0’这样!岛屿的数量其实就是遍历过程中找到’1’的次数!classSolution{public:voiddfs(vectorvectorchargrid,intr,intc){intnrgrid.size();intncgrid[0].size();if(grid[r][c]0)return;grid[r][c]0;if(r1nrgrid[r1][c]1)dfs(grid,r1,c);if(r-10grid[r-1][c]1)dfs(grid,r-1,c);if(c1ncgrid[r][c1]1)dfs(grid,r,c1);if(c-10grid[r][c-1]1)dfs(grid,r,c-1);}intnumIslands(vectorvectorchargrid){intnrgrid.size();if(!nr)return0;intncgrid[0].size();intnum_islands0;for(intr0;rnr;r){for(intc0;cnc;c){if(grid[r][c]1){num_islands;dfs(grid,r,c);}}}returnnum_islands;}};695.岛屿的最大面积与上同理classSolution{public:intdfs(vectorvectorintgrid,intr,intc){intnrgrid.size();intncgrid[0].size();if(grid[r][c]0)return0;intsumgrid[r][c];grid[r][c]0;//记得置0不然会stack-overflow!if(r1nrgrid[r1][c]1)sumdfs(grid,r1,c);if(r-10grid[r-1][c]1)sumdfs(grid,r-1,c);if(c1ncgrid[r][c1]1)sumdfs(grid,r,c1);if(c-10grid[r][c-1]1)sumdfs(grid,r,c-1);returnsum;}intmaxAreaOfIsland(vectorvectorintgrid){intnrgrid.size();if(!nr)return0;intncgrid[0].size();intres0;for(intr0;rnr;r){for(intc0;cnc;c){if(grid[r][c]1){resmax(dfs(grid,r,c),res);}}}returnres;}};