LeetCode 1254 Number of Closed Islands

Tag: 岛屿问题 LeetCode Posted on 2022-02-02 16:46:20 Edited on 2022-02-05 16:54:15 Views: 189

题目分析

https://leetcode.com/problems/number-of-closed-islands/

与 LeetCode 200 Number of Islands 类似,只不过这次靠边的岛屿不算了。

深度优先搜索

真的离谱,200 号题目里 grid 是 char 数组,这里是 int 数组,看了半天才看出问题来。 除此之外,还有边界写错(忘记 -1),= 写成 ==。

class Solution {
public:
    int closedIsland(vector<vector<int>>& 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] == 0) {
                    if (travelIsland(i, j, grid)) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
    
    bool travelIsland(int i, int j, vector<vector<int>>& grid) {
        if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()) return false;
        if (grid[i][j] == 0) {
            grid[i][j] = 2; // mark as visited island
            bool f1 = travelIsland(i+1, j, grid);
            bool f2 = travelIsland(i-1, j, grid);
            bool f3 = travelIsland(i, j+1, grid);
            bool f4 = travelIsland(i, j-1, grid);
            return f1 && f2 && f3 && f4;
        }
        return true;
    }
};

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