力扣
200. 岛屿数量
一、题目解析：
这是一个非常经典的迷宫图上的联通分量的题目。什么是连通分量：就是说一个点通过上下左右连成一片。
本题的最终问题为：求解陆地这个联通分量的数量，因此外面只需要把所有的连通分量找出来即可。
如何求解联通分量的数目？
我们可以用搜索法来求解。从一个点开始找到和这个点相连的所有的点作为一个联通分量，这很明显就是DFS和BFS的应用。如何判断有多少个来联通分量呢？我们可以设置一个外层的for循环来进行遍历，假设连通分量的初始数目为0，如果这个点之前没有访问过，就给联通分量的数目加1，然后就从这个点开始进行DFS搜索，找到这个点的所有连接点作为一个连通分量；如果这个点之前访问过，我们就不给联通分量数目加1。直到找到新的没有访问过的点，然后才给这个数目加1，然后继续从这个点开始进行DFS搜索。
空间问题：
我们可以设置一个额外的数组来记录某个点是否被访问过，但是我们可以进行空间优化：因为已经访问过的点对我们没有任何意义了，所以我们可以直接把它设为0，也就是水。
一个思维误区：
之前我的想法是找到所有的联通分量之后，然后再去判断这个联通分量是否满足四周被水包围的条件。但是这个其实是完全没有必要的，因为我们在找连通分量的过程中，只有符合要求（没有越界或者该邻接点为水）的才会被加入到这个连通分量的块中，如果不符合要求，就返回了。所以没有必要去加这一步。如图，其实这个题就是求连通分量的总个数而已。
二、算法代码
class
Solution {
public
:
int
n,m;
int
count=
0
;
//
记录岛屿的数量
int
dx[
4
] = {
0
,
0
,-
1
,
1
};
int
dy[
4
] = {
1
,-
1
,
0
,
0
};
//
按照上下左右的方向进行搜索，注意
dx
和
dy
的对应关系
void
dfs(
int
x,
int
y ,vector<vector<
char
>>& g )
{
if
(x<
0
|| y<
0
|| x >= m || y>=n ||g[x][y]==
‘0’
)
//
判断是否越界及是否已经访问过
return
;
g[x][y] =
‘0’
;
//
将访问过的点置
0
for
(
int
k =
0
;k<
4
;k++)
{
dfs(x+dx[k],y+dy[k],g);
}
}
int
numIslands(vector<vector<
char
>>& grid) {
if
( grid.size()==
0
|| grid[
0
].size()==
0
)
return
0
;
m = grid.size();
//
二维数组的行数
n = grid[
0
].size();
//
二维数组的列数
//
判断给出的二维数组是否为空
for
(
int
i =
0
;i<m;i++)
//
对二维数组进行遍历
{
for
(
int
j =
0
;j<n;j++)
{
if
(grid[i][j]==
‘1’
)
{
dfs(i ,j ,grid );
count++;
}
}
}
return
count;
}
};