深度优先遍历

求连通块数量。可以遍历所有格子，当格子是岛屿，对岛屿深度优先遍历，找到整个岛，并且将遍历的岛屿标记，以免重复遍历，或递归死循环。标记可以使用状态数组，也可以修改格子的值。本题可以修改格子的值，更为直观与节约空间。

遍历小技巧 : 开方向数组 $dx、dy$ 对应上右下左四个方向，深搜每个格子时，代码一步到位。

class Solution {
public:int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};int n,m;int numIslands(vector<vector<char>>& grid) {n = grid.size(),m = grid[0].size();int ans = 0;for(int i = 0;i<n;i++)for(int j = 0;j<m;j++)if('1'==grid[i][j]) ans++,dfs(i,j,grid);return ans;}void dfs(int x,int y,vector<vector<char>> &grid){grid[x][y] = '0';for(int i = 0;i<4;i++){int a = x + dx[i],b = y + dy[i];if(a>=0&&a<n&&b>=0&&b<m&&'1'==grid[a][b]) dfs(a,b,grid);}}
};

1. 时间复杂度 : $O(n)$ ， $n$ 是行数， $m$ 是列数，最多遍历所有点两次，时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(n)$ ， 函数压栈的最坏深度为 $O(n)$ 。

AC

致语

• 理解思路很重要！
• 欢迎读者在评论区留言，墨染看到就会回复的。