分析：经典连通分量问题

图：

　　节点：所有1的位置

　　边：两个相邻的1的位置有一条边

BFS／DFS (DFS使用递归，代码较短)

　　选一个没标记的点，然后搜索，扩展4个邻居（如果有），直到不能扩展

　　每一次是一个连通分量

　　难点：标记节点——判重

C++

DFS

1 class Solution { 2 public: 3     void help(vector
     
      
       >& a, int x, int y) { 4         if ((x < 0) || (x >= a.size()) || (y < 0) || (y >= a[x].size()) || a[x][y] == false) { 5             return ; 6         } 7         a[x][y] = false; 8         help(a, x + 1, y); 9         help(a, x - 1, y);10         help(a, x, y + 1);11         help(a, x, y - 1);12     }13     /**14      * @param grid a boolean 2D matrix15      * @return an integer16      */17     int numIslands(vector
       
        
         >& grid) {18         // Write your code here19         int ans = 0;20         for (int i = 0; i < grid.size(); ++i) {21             for (int j = 0; j < grid[i].size(); ++j) {22                 if (grid[i][j] == true) {23                     help(grid, i, j);24                     ++ans;25                 }26             }27         }28         return ans;29     }30 };
        
       
      
     

C++

BFS

1 class Solution { 2 public: 3     void help(vector
     
      
       >& a, int x, int y) { 4         queue
       
        
          > q; 5         const int dx[] = {-1, 1, 0, 0}; 6         const int dy[] = {
   0, 0, -1, 1}; 7         a[x][y] = false; 8         for (q.push(make_pair(x, y)); !q.empty(); q.pop()) { 9             x = q.front().first;10             y = q.front().second;11             for (int i = 0; i < 4; ++i) {12                 int nx = x + dx[i];13                 int ny = y + dy[i];14                 if ((nx >= 0) && (nx < a.size()) && (ny >= 0) &&(ny < a[nx].size()) && (a[nx][ny] == true)) {15                     a[nx][ny] = false;16                     q.push(make_pair(nx, ny));17                 }18             }19         }20     }21     /**22      * @param grid a boolean 2D matrix23      * @return an integer24      */25     int numIslands(vector
         
          
           >& grid) {26 // Write your code here27 int ans = 0;28 for (int i = 0; i < grid.size(); ++i) {29 for (int j = 0; j < grid[i].size(); ++j) {30 if (grid[i][j] == true) {31 help(grid, i, j);32 ++ans;33 }34 }35 }36 return ans;37 }38 };