分析：经典连通分量问题
图：
节点：所有1的位置
边：两个相邻的1的位置有一条边
BFS／DFS (DFS使用递归，代码较短)
选一个没标记的点，然后搜索，扩展4个邻居（如果有），直到不能扩展
每一次是一个连通分量
难点：标记节点——判重
C++
DFS
1 class Solution { 2 public: 3 void help(vector<vector<bool>>& 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 matrix 15 * @return an integer 16 */ 17 int numIslands(vector<vector<bool>>& grid) { 18 // Write your code here 19 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<vector<bool>>& a, int x, int y) { 4 queue<pair<int, int> > 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 matrix 23 * @return an integer 24 */ 25 int numIslands(vector<vector<bool>>& grid) { 26 // Write your code here 27 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 };
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/5012230.html，如需转载请自行联系原作者
