LeetCode 200 Number of Islands

Tag: 岛屿问题 LeetCode Posted on 2022-02-02 16:44:11 Edited on 2022-02-05 16:54:27 Views: 137

题目分析

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);
        }
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/