LeetCode Number of Islands 岛的数量（DFS，BFS）

题意：0代表水，1代表陆地，那么被水围起来的就是岛了，给一个01矩阵，问有多少个岛？

思路：DFS还是比较短，实现了一下。如果一个点已经被遍历过了，那就将其置为0就行了，不要去搜0的。

 class Solution {

 public:

     bool isok(vector<vector<char> >& grid,int x,int y)

     {

         return x>= && y>= && x<grid.size() && y<grid[].size();

     }

     void DFS( vector<vector<char> >& grid,int x,int y )

     {

         if( !isok(grid,x,y) || grid[x][y]==''  )   return ;

         grid[x][y]='';

         DFS( grid, x, y+ );

         DFS( grid, x, y- );

         DFS( grid, x+, y );

         DFS( grid, x-, y );

     }

     int numIslands(vector<vector<char> >& grid) {

         int ans=;

         for(int i=; i<grid.size(); i++)

         {

             for(int j=; j<grid[].size(); j++)

             {

                 if(grid[i][j]=='')

                 {

                     DFS(grid, i, j);

                     ans++;

                 }

             }

         }

         return ans;

     }

 };

AC代码

巴特西

LeetCode Number of Islands 岛的数量（DFS，BFS）

最新文章

热门文章