Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110 11010 11000 00000

Answer: 1

Example 2:

11000 11000 00100 00011

Answer: 3

 

思路：与的思路是一样的，也可以用广度和深度优先搜索。当遇到1的时候，把区域数加1，并把与这个1相连的整片区域标记为2.

下面的BFS用时25ms，DFS用时16ms

int numIslands(vector
     
      
       >& grid) {        if(grid.empty()) return 0;        int num = 0;        for(int i = 0; i < grid.size(); ++i)            for(int j = 0; j < grid[0].size(); ++j)                if(grid[i][j] == '1')                {                    num++;                    BFS(grid, i, j);                }        return num;    }    void BFS(vector
       
        
         >& grid, int r, int c)    {        queue
         
          
           > q; q.push(make_pair(r, c)); while(!q.empty()) { int i = q.front().first; int j = q.front().second; q.pop(); if(i >= 0 && j >= 0 && i < grid.size() && j < grid[0].size() && grid[i][j] == '1') { grid[i][j] = 2; q.push(make_pair(i - 1, j)); q.push(make_pair(i + 1, j)); q.push(make_pair(i, j - 1)); q.push(make_pair(i, j + 1)); } } } void DFS(vector
           
            
             >& grid, int r, int c) { if(r >= 0 && c >= 0 && r < grid.size() && c < grid[0].size() && grid[r][c] == '1') { grid[r][c] = 2; DFS(grid, r - 1, c); DFS(grid, r + 1, c); DFS(grid, r, c - 1); DFS(grid, r, c + 1); } }
            
           
          
         
        
       
      
     

 

很奇怪的是，开始我写的时候BFS多传了一个变量就TLE了？？为什么呢？？

int numIslands(vector
     
      
       >& grid) {        if(grid.empty()) return 0;        int num = 0;        for(int i = 0; i < grid.size(); ++i)        {            for(int j = 0; j < grid[0].size(); ++j)            {                if(grid[i][j] == '1')                    BFS(grid, i, j, num);            }        }        return num;    }    void BFS(vector
       
        
         >& grid, int r, int c, int &num)    {        num++;        queue
         
          
           > q; q.push(make_pair(r, c)); while(!q.empty()) { int i = q.front().first; int j = q.front().second; q.pop(); if(i >= 0 && j >= 0 && i < grid.size() && j < grid[0].size() && grid[i][j] == '1') { grid[i][j] = num + 1; q.push(make_pair(i - 1, j)); q.push(make_pair(i + 1, j)); q.push(make_pair(i, j - 1)); q.push(make_pair(i, j + 1)); } } }