433-岛屿的个数
思路
使用深度优先遍历，如果某点未被遍历过，则表示它处于一个新岛屿上，此时遍历与其在同一岛屿上的点
code
class Solution {
public:
/**
* @param grid a boolean 2D matrix
* @return an integer
*/
int numIslands(vector<vector<bool>>& grid) {
// Write your code here
int sizeRow = grid.size();
if (sizeRow <= 0) {
return 0;
}
int sizeCol = grid[0].size();
if (sizeCol <= 0) {
return 0;
}
int count = 0;
vector<vector<bool>> isVisited(sizeRow, vector<bool>(sizeCol, false));
for (int i = 0; i < sizeRow; i++) {
for (int j = 0; j < sizeCol; j++) {
if (grid[i][j] == true && !isVisited[i][j]) {
numIslands(i, j, grid, isVisited);
count++;
}
}
}
return count;
}
void numIslands(int i, int j, vector<vector<bool>> &grid, vector<vector<bool>> &isVisited) {
if (i < 0 || i >= grid.size()) {
return;
}
if (j < 0 || j >= grid[0].size()) {
return;
}
if (grid[i][j] == false || isVisited[i][j] == true) {
return;
}
isVisited[i][j] = true;
numIslands(i - 1, j, grid, isVisited);
numIslands(i + 1, j, grid, isVisited);
numIslands(i, j - 1, grid, isVisited);
numIslands(i, j + 1, grid, isVisited);
}
};