|
小明最近看修真小说看多了，晚上做梦都梦到自己变成了掌控一方地域的上古大能，这片地域湖泊星罗棋布，数不胜数。他神识一释放，这片地域的二维平面地图就展现在他的脑海中，地域被切割成一个M*N的二维矩阵，有水的格子标记为字符“S”，没水的格子标记为“H”。你能快速帮小明计算出湖泊的个数吗？说明：被“H”和边界包围起来的若干个相邻“S”成为一个湖泊。
输入描述：
第一行输入M，N（逗号分隔），代表M* N的二维矩阵。
然后接下来输入M个字符串，每个字符串都是N个字符，字符只能是“S”或者“H”
取值范围：0<M，N<1000
示例1
输入
4,5
SSHHH
SSHHH
HHSHH
HHHSS
输出
3
备注：被“H”和边界包围起来的若干个相邻的“S”称为一个湖泊
思路：类似于leetcode200岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
应用DFS算法，即深度优先遍历：不断地沿着bai顶点的深度方向遍历，顶点的深度方向是指它的邻接点方向。
深度优先遍历（DFS）实现步骤：
1、从顶点出发。
2、访问顶点，也就是根节点。
3、依次从顶点的未被访问的邻接点出发，进行深度优先遍历；直至和顶点有路径相通的顶点都被访问。
4、若此时尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到所有顶点均被访问过为止。
解题思路
使用DFS解决。遍历二维数组，遇到陆地的时候则岛屿数量+1，同时使用DFS消除与此岛屿相连的所有陆地，然后继续遍历二维数组，如果又碰到陆地，说明是一个新的岛，消除与之相连的陆地，继续遍历，同理直到遍历完毕。
class Solution {
private:
void dfs(vector<vector<char>>& grid, int r, int c) {
int nr = grid.size();
int nc = grid[0].size();
grid[r][c] = '0'; //将岛屿置为0
//以下四步的作用：防止数组越界，并且将相邻岛屿置为0
if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
}
public:
int numIslands(vector<vector<char>>& grid) {
int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') { //找到一个1说明又找到一个岛屿
num_islands++;
dfs(grid, r, c); //将与它相邻的岛屿置为0
}
}
}
return num_islands;
}
};
| 
转播
