LeetCode200. 岛屿数量( DFS , 回溯 )

1. 本题的意思是连在一起的陆地都算做一个岛屿，本题可以采用类似渲染的做法，尝试以每个点作为渲染的起点，可以渲染的陆 地都算做一个岛屿，最后看渲染了多少次，即深度优先算法执行了多少次。

2.我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 2。最终岛屿的数量就是我们进行深度优先搜索的次数。

class Solution {
public:
     int dir[4][2] = {1,0,-1,0,0,1,0,-1};
   
    void DFS(vector<vector<char>>& grid , int row , int col , int x , int y)
    {
       grid[x][y] = '2'; //处理当前逻辑， 设置为读取过

       for(auto& e : dir) //遍历每一种可能，四个方向
       {
           int newx = x + e[0];
           int newy = y + e[1];

           if(newx < 0 || newx >= row || newy < 0 || newy >= col || grid[newx][newy] != '1')
           continue;

           DFS(grid , row ,col , newx , newy); //只有是 ‘1’ 的才能继续渲染
       }
    }

    int numIslands(vector<vector<char>>& grid) 
    {
       int row = grid.size();
       int col = grid[0].size();
       int num = 0;

       for(int i = 0 ; i < row ; ++i)
       {
           for(int j = 0 ; j < col ; ++j)
           {
               if(grid[i][j] == '1') //以找到的第一个 ‘1’ 作为渲染起始点
               {
                   DFS(grid , row ,col , i , j);
                   num++;
               }
           }
       }

       return num;
    }
};