200. 岛屿数量
class Solution { public: int numIslands(vector<vector<char>>& grid) { int i, j, lr, lc; lr = grid.size(); if(!lr) return 0; lc = grid[0].size(); int island = 0; for(i = 0; i < lr; i++) { for(j = 0; j < lc; j++) { if(grid[i][j] == ‘1‘ && dfs(grid, i, j, lr, lc) >= 1) island++; } } return island; } int dfs(vector<vector<char>>&grid, int i, int j, int lr, int lc) { if(i<0||i>=lr||j<0||j>=lc) return 0; if(grid[i][j]==‘1‘) { grid[i][j] = ‘0‘; return dfs(grid, i-1, j, lr, lc)+dfs(grid, i+1, j, lr, lc)+dfs(grid, i, j-1, lr, lc)+dfs(grid, i, j+1, lr, lc)+1; } else return 0; } };
思路：BFS 借助队列
class Solution { struct Node{ int x, y; }node; int X[4] = {-1, 1, 0, 0}; int Y[4] = {0, 0, -1, 1}; public: int numIslands(vector<vector<char>>& grid) { int i, j, lr, lc; lr = grid.size(); if(!lr) return 0; lc = grid[0].size(); int island = 0; for(i = 0; i < lr; i++) { for(j = 0; j < lc; j++) { if(grid[i][j] == ‘1‘) { if(bfs(grid, i, j, lr, lc)>=1) island++; } } } return island; } int bfs(vector<vector<char>> &grid, int i, int j, int lr, int lc) { int count = 0; queue<Node> Q; node.x = i; node.y = j; Q.push(node); count++; grid[i][j] = ‘0‘; while(!Q.empty()) { Node top = Q.front(); Q.pop(); for(int k = 0; k < 4; k++) { node.x = top.x + X[k]; node.y = top.y + Y[k]; if(node.x>=0&&node.x<lr&&node.y>=0&&node.y<lc&&grid[node.x][node.y]==‘1‘) { Q.push(node); grid[node.x][node.y] = ‘0‘; count++; } } } return count; } };
原文：https://www.cnblogs.com/jessica216/p/13423816.html