本文共 2304 字，大约阅读时间需要 7 分钟。
分析：经典连通分量问题
图：
节点：所有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 };
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/5012230.html，如需转载请自行联系原作者