This is a typical problem about searching. In fact, you can use either BFS or DFS for it. Personally, I use BFS because I think it is more intuitive and easy to implement.

The idea is fairly simple. We maintain another 2-dimensional vector visited to mark whether the corresponding position in grid has been visited and a variable count for the number of islands (initialized to be 0). Then we visit grid from left to right and top to bottom. Each time when we see a non-visited 1 in grid, we add the number of islands by 1 and mark all the connected 4-neighbors (BFS is applied here to get neighbors, neighbors of neighbors, neighbors of neighbors of neighbors, ...) of the non-visited 1 (including itself) as visited.

Note that a lot of the solutions in the discussion forum directly changes 1 in grid to 0 instead of using another 2-dimensional vector visited. However, I personally prefer to keep the input unchanged in a function with a return value.

The code is as follows.

1 class Solution { 2 public: 3     int numIslands(vector
     
      
       >& grid) { 4         if (grid.empty()) return 0; 5         int m = grid.size(), n = grid[0].size(); 6         vector
       
        
          > visited(m, vector
         
           (n, false)); 7         int count = 0; 8         for (int i = 0; i < m; i++) { 9             for (int j = 0; j < n; j++) {10                 if (grid[i][j] == '1' && !visited[i][j]){11                     count++;12                     markIslands(grid, visited, i, j);13                 }14             }15         }16         return count;17     }18 private:19     void markIslands(vector
          
           
             >& grid, vector
            
             
               >& visited, int row, int col) {20 visited[row][col] = true;21 if (row - 1 >= 0 && grid[row - 1][col] == '1' && !visited[row - 1][col])22 markIslands(grid, visited, row - 1, col);23 if (row + 1 < grid.size() && grid[row + 1][col] == '1' && !visited[row + 1][col])24 markIslands(grid, visited, row + 1, col);25 if (col - 1 >= 0 && grid[row][col - 1] == '1' && !visited[row][col - 1])26 markIslands(grid, visited, row, col - 1);27 if (col + 1 < grid[0].size() && grid[row][col + 1] == '1' && !visited[row][col + 1])28 markIslands(grid, visited, row, col + 1);29 }30 };