岛屿数量
给你一个由 '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
思路
flood fill泛洪算法+dfs
首先我们使用两层for循环遍历二维数组grid，当遇到'1'的时候，标记遇到了“岛屿”，此时岛屿数量加1
然后触发dfs，先将当前位置（是'1'）设为'0',在遇到'1'的位置的上下左右搜索。如果碰到'1'，说明该位置仍是目前发现的岛屿的一部分陆地，将其改为'0'，如果碰到'0'就不管，说明该位置是水不是陆地。
上述操作就是flood fill中的“同化”操作
dfs结束后，当前位置的上下左右都变成了'0'（包括当前位置本身），然后for循环会继续向后遍历，直到再次碰到'1'(即陆地)，然后通过一样的方法统计陆地数量并使用dfs同化。
当二维数组grid遍历完成，那么岛屿的数量也就统计完成了。
疑问
以下是解答1，该代码可以通过测试
class Solution {
public:
int row, col;
int dx[4] = {-1,0,1,0};//如果记不住，可以假设一个(1,1)，然后通过加减1来确定对应偏移量
int dy[4] = {0,-1,0,1};
int numIslands(vector<vector<char>>& grid) {
int res = 0;
row = grid.size();//行
col = grid[0].size();//列
for(int x = 0; x < row; ++x){//遍历grid，寻找陆地'1'
for(int y = 0; y < col; ++y){
if(grid[x][y] == '1'){//找到陆地之后，同化其上下左右四个方向的区域为'0'
dfs(grid, x, y);//调用递归实现
res++;//记录岛屿数量
}
}
}
return res;
}
void dfs(vector<vector<char>>& grid, int x, int y){
grid[x][y] = '0';
for(int i = 0; i < 4; ++i){//循环四次，使用偏移量计算出当前位置的上下左右位置的坐标
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == '1'){
dfs(grid, nx, ny);//这里其实已经给递归设置了结束条件，如果不满足上面的if的话是不会进入递归的
}
}
}
};
下面是我的解答代码，我也使用了同样的思想，但是为什么我的代码会超时
#include <ratio>
class Solution {
public:
void dfs(vector<vector<char> >& grid, int x, int y, int row, int col){
//递归终止条件
if(x < 0 || x >= row || y < 0 || y >= col || grid[x][y] == '0') return;
//单层处理逻辑
grid[x][y] = '0';
dfs(grid, x - 1, y, row, col);
dfs(grid, x + 1, y, row, col);
dfs(grid, x, y - 1, row, col);
dfs(grid, x, y + 1, row, col);
return;
}
int solve(vector<vector<char> >& grid) {
// write code here
if(grid.size() == 0) return 0;
int row = grid.size();
int col = grid[0].size();
int res = 0;
for(int x = 0; x < row; ++x){
for(int y = 0; y < col; ++y){
if(grid[x][y] == '1'){
res += 1;
dfs(grid, x, y, row, col);
}
}
}
return res;
}
};
原因
这个主要是代码实现的问题，思路是一样的，都是基于flood fill泛洪算法+dfs实现
我的代码中，递归中遍历的东西太多，加上递归深度比较深，所以出现了栈溢出的问题
例如，在实现flood fill中"同化"操作时，我的代码需要对上下左右进行四次递归才能将所有情况尝试一遍，这就产生了巨大的开销
优化
使用偏移量来简化对四个方向的搜索
用dx和dy数组来表示上下左右四个方向的偏移量。通过对当前位置 (x, y) 分别加上 dx[i] 和 dy[i]，可以得到该方向的相邻位置 (nx, ny)。
for(int i = 0; i < 4; ++i){
int nx = x + dx[i];//由当前位置坐标加上偏移量计算得到的上下左右的坐标
int ny = y + dy[i];
if(nx >= 0 && nx < row && ny >= 0 && ny < col && grid[nx][ny] == '1'){
dfs(grid, nx, ny);
}
}
这样优化之后，我们只需要循环4次，计算四个方向的坐标，然后每次调用一个递归函数就可以实现对四个方向的搜索
减少了递归深度
举个例子来说明，假设当前位置为
(1, 1)，则根据dx和dy数组中的元素，可以得到下面四个相邻位置：
- 上方位置：
(1 + dx[0], 1 + dy[0]) = (1 - 1, 1 + 0) = (0, 1)- 左方位置：
(1 + dx[1], 1 + dy[1]) = (1 + 0, 1 - 1) = (1, 0)- 下方位置：
(1 + dx[2], 1 + dy[2]) = (1 + 1, 1 + 0) = (2, 1)- 右方位置：
(1 + dx[3], 1 + dy[3]) = (1 + 0, 1 + 1) = (1, 2)可以看到，通过不同的
dx[i]和dy[i]组合，可以分别表示上下左右四个方向的移动。其中，
dx[0] = -1代表向上移动，dx[1] = 0代表向左移动，dx[2] = 1代表向下移动，dx[3] = 0代表向右移动。类似地，
dy[0] = 0、dy[1] = -1、dy[2] = 0、dy[3] = 1分别对应着上下左右四个方向的纵向偏移量。