9.17 DFS中等 200 Number of Islands
200 Number of Islands【DFS函数默写,递归思路学习】
使用 DFS递归的思路:不需要确定具体方向,直接上下左右全面开花,如果不满足探索条件就直接暂停递归,如果满足探索条件就直接在新的数组中进行标记。所以探索条件是:在matrix范围内+不为海水‘1’+没有探索过island==0
class Solution {
public:void DFS(vector<vector<char>>& grid ,vector<vector<int>>& island, int i ,int j){int m = grid.size();int n = grid[0].size();//过滤条件判断,确保在矩阵内,且当前点是陆地且未被访问if(i<0 || i >= m || j<0 || j>=n || grid[i][j] == '0' || island[i][j] == 1) return ;//满足探索条件island[i][j] = 1;// 递归访问四个方向DFS(grid, island, i - 1, j); // 上DFS(grid, island, i + 1, j); // 下DFS(grid, island, i, j - 1); // 左DFS(grid, island, i, j + 1); // 右}int numIslands(vector<vector<char>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<int>> island(m , vector<int>(n,0));int num = 0;for(int i = 0 ; i < m ; i++){for(int j = 0; j < n ; j++){//没遇过的岛屿if(grid[i][j] == '1' && island[i][j] == 0){//探索岛屿DFS(grid,island , i , j);num++;}}}return num;}};