LeetCode：深度优先搜索DFS

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. 先遍历网格，若元素为’1’则可以以此点展开dfs操作；
2. dfs操作：深度优先搜索过程中将搜索到的’1’都写为‘0’；
3. 这样!岛屿的数量其实就是遍历过程中找到’1’的次数!

classSolution{public:voiddfs(vector<vector<char>>&grid,intr,intc){intnr=grid.size();intnc=grid[0].size();if(grid[r][c]=='0')return;grid[r][c]='0';if(r+1<nr&&grid[r+1][c]=='1')dfs(grid,r+1,c);if(r-1>=0&&grid[r-1][c]=='1')dfs(grid,r-1,c);if(c+1<nc&&grid[r][c+1]=='1')dfs(grid,r,c+1);if(c-1>=0&&grid[r][c-1]=='1')dfs(grid,r,c-1);}intnumIslands(vector<vector<char>>&grid){intnr=grid.size();if(!nr)return0;intnc=grid[0].size();intnum_islands=0;for(intr=0;r<nr;r++){for(intc=0;c<nc;c++){if(grid[r][c]=='1'){num_islands++;dfs(grid,r,c);}}}returnnum_islands;}};

695.岛屿的最大面积

与上同理

classSolution{public:intdfs(vector<vector<int>>&grid,intr,intc){intnr=grid.size();intnc=grid[0].size();if(grid[r][c]==0)return0;intsum=grid[r][c];grid[r][c]=0;//记得置0！不然会stack-overflow!if(r+1<nr&&grid[r+1][c]==1)sum+=dfs(grid,r+1,c);if(r-1>=0&&grid[r-1][c]==1)sum+=dfs(grid,r-1,c);if(c+1<nc&&grid[r][c+1]==1)sum+=dfs(grid,r,c+1);if(c-1>=0&&grid[r][c-1]==1)sum+=dfs(grid,r,c-1);returnsum;}intmaxAreaOfIsland(vector<vector<int>>&grid){intnr=grid.size();if(!nr)return0;intnc=grid[0].size();intres=0;for(intr=0;r<nr;r++){for(intc=0;c<nc;c++){if(grid[r][c]==1){res=max(dfs(grid,r,c),res);}}}returnres;}};