LeetCode 200 Number of Islands
题目分析
https://leetcode.com/problems/number-of-islands/
遍历所有元素，如果是没访问过的岛屿的元素，就完整的访问一遍该岛屿。
深度优先搜索
时间复杂度 O(mn)，空间复杂度 O(1)
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i=0; i<grid.size(); i++) {
for (int j=0; j<grid[0].size(); j++) {
if (grid[i][j] == '1') {
count += 1;
// dfs this new island
travelIsland(i, j, grid);
}
}
}
return count;
}
void travelIsland(int i, int j, vector<vector<char>>& grid) {
if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) return;
if (grid[i][j] == '1') {
grid[i][j] = '2'; // mark as visited land
travelIsland(i+1, j, grid);
travelIsland(i-1, j, grid);
travelIsland(i, j+1, grid);
travelIsland(i, j-1, grid);
}
}
};