Leetcode每日一题 —— 1254. 统计封闭岛屿的数目

魔法师 2026-10-25 08:42 1

思路

遍历内部，与到没访问过得陆地grid[i][j]==0开始DFS。DFS中：

遇到边界直接返回false

标记当前位置为已访问grid[i][j]=-1

如果上下左右是陆地则继续遍历它是否是陆地

如果DFS最终返回true则结果+1

代码

class Solution {

    private int[][] grid;

    public int closedIsland(int[][] grid) {

        this.grid = grid;

        int m = grid.length;

        int n = grid[0].length;

        int ans = 0;

        // 寻找未访问过的陆地开始DFS

        for (int i = 1; i < m - 1; i++) {

            for (int j = 1; j < n - 1; j++) {

                if (grid[i][j] == 0) {

                    if (dfs(i, j)) {

                        ans++;

                    }

                }

            }

        }

        return ans;

    }

    private boolean dfs(int i, int j) {

        // 到边界了，返回false

        if (i == 0 || i == grid.length - 1 || j == 0 || j == grid[0].length - 1) {

            return false;

        }

        // 标记已访问

        grid[i][j] = -1;

        

        // 递归搜索四个方向

        boolean res = true;

        if (grid[i + 1][j] == 0) {

            res &= dfs(i + 1, j);

        }

        if (grid[i - 1][j] == 0) {

            res &= dfs(i - 1, j);

        }

        if (grid[i][j + 1] == 0) {

            res &= dfs(i, j + 1);

        }

        if (grid[i][j - 1] == 0) {

            res &= dfs(i, j - 1);

        }

        return res;

    }

}

最新回复 (8)

Lvvvv 10-25 09:17

1楼

bfs写法。怎么这么慢O.o…

class Solution {

public:

    int closedIsland(vector<vector<int>>& grid) {

        int res = 0;

        static vector<int> dx = {0,1,0,-1}, dy = {1,0,-1,0};

        int m = grid.size(), n = grid[0].size();

        auto bfs = [&](int x, int y) -> int {

            queue<int> q;

            int ok = 1;

            q.push(x * n + y);

            grid[x][y] = 1;

            while(q.size()) {

                auto t = q.front();

                q.pop();

                for(int i = 0; i < 4; i++) {

                    int nx = t / n + dx[i], ny = t % n + dy[i];

                    if(nx < 0 || nx >= m || ny < 0 || ny >= n) {

                        ok = 0;

                        continue;

                    }

                    if(grid[nx][ny] == 0) {

                        grid[nx][ny] = 1;

                        q.push(nx * n + ny);

                    }

                }

            }

            return ok;

        };

        for(int i = 0; i < m; i++) {

            for(int j = 0; j < n; j++) {

                if(grid[i][j] == 0) {

                    res += bfs(i,j);

                }

            }

        }

        return res;

    }

};

带带大袋鼠 10-25 09:19

2楼

嘿嘿，刷到过原题，秒了

SomeBottle 10-25 09:52

3楼

用并查集糊了一个。

class Solution {

public:

    int closedIsland(vector<vector<int>>& grid) {

        int m=grid.size(),n=grid[0].size();

        // 找连通块数量，但是要排除边上的 0

        int cnt=m*n;

        vector<int> parents(m*n,-1);

        vector<int> sizes(m*n,1);

        auto find=[&](this auto&& self,int x)->int {

            return parents[x]<0 ? x : parents[x]=self(parents[x]);

        };

        auto merge=[&](int x1,int x2)->void {

            int root1=find(x1),root2=find(x2);

            if(root1==root2){

                return;

            }

            bool invalid=parents[root1]==-2||parents[root2]==-2;

            if(sizes[root1]<sizes[root2]){

                swap(root1,root2);

            }

            parents[root2]=root1;

            sizes[root1]+=sizes[root2];

            // 状态传递

            if(invalid){

                parents[root1]=-2;

            }

        };

        // 开始执行合并

        for(int i=0;i<m;i++){

            for (int j=0;j<n;j++){

                int idx=i*n+j;

                if(grid[i][j]==1){

                    // 是 1，忽略

                    parents[idx]=-2;

                    continue;

                }

                // 是 0，但在边缘上，同样忽略这个块

                if(i==0||i==m-1||j==0||j==n-1){

                    parents[find(idx)]=-2;

                }

                // 合并 0

                if(i<m-1&&grid[i+1][j]==0){

                    merge(idx,(i+1)*n+j);

                }

                if(j<n-1&&grid[i][j+1]==0){

                    merge(idx,i*n+j+1);

                }

            }

        }

        // 扫描 parents 统计 -1 数量

        int res=0;

        for(int p:parents){

            if(p==-1){

                res++;

            }

        }

        return res;

    }

};

欧拉线 10-25 10:23

4楼

static void dfs(int** grid, int m, int n, int r, int c) {

	if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 1)

		return;

	grid[r][c] = 1;  // 标记为已访问

	dfs(grid, m, n, r - 1, c);

	dfs(grid, m, n, r + 1, c);

	dfs(grid, m, n, r, c - 1);

	dfs(grid, m, n, r, c + 1);

}



int closedIsland(int** grid, int gridSize, int* gridColSize) {

	int m = gridSize;

	int n = gridColSize[0];

	int ans = 0;

	// 去除所有与边界相连的土地

	for (int i = 0; i < m; i++) {

		for (int j = 0; j < n; j++) {

			if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) &&

			    grid[i][j] == 0) {

				dfs(grid, m, n, i, j);

			}

		}

	}

	// 剩余的土地都属于封闭岛屿

	for (int i = 1; i < m - 1; i++) {

		for (int j = 1; j < n - 1; j++) {

			if (grid[i][j] == 0) {

				ans++;

				dfs(grid, m, n, i, j);

			}

		}

	}

	return ans;

}

咪帕 10-25 11:19

5楼

非封闭岛屿标成水, 然后BFS遍历

class Solution {

public:

    int closedIsland(vector<vector<int>>& grid) {

        int m = grid.size(), n = grid[0].size();

        queue<pair<int, int>> q;

        vector<pair<int, int>> directions{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

        auto bfs = [&]() {

            while (!q.empty()) {

                auto [x, y] = q.front(); q.pop();

                for (auto [dx, dy]: directions) {

                    int nx = x + dx, ny = y + dy;

                    if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] == 1) continue;

                    grid[nx][ny] = 1;

                    q.emplace(nx, ny);

                }

            }

        };

        for (int i = 0; i < m; i++) {

            if (grid[i][0] == 0) {

                q.emplace(i, 0);

                grid[i][0] = 1;

                bfs();

            }

            if (grid[i][n-1] == 0) {

                q.emplace(i, n-1);

                grid[i][n-1] = 1;

                bfs();

            }

        }

        for (int i = 0; i < n; i++) {

            if (grid[0][i] == 0) {

                q.emplace(0, i);

                grid[0][i] = 1;

                bfs();

            }

            if (grid[m-1][i] == 0) {

                q.emplace(m-1, i);

                grid[m-1][i] = 1;

                bfs();

            }

        }

        int cnt = 0;

        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {

                if (grid[i][j] == 0) {

                    q.emplace(i, j);

                    grid[i][j] = 1;

                    bfs();

                    cnt++;

                }

            }

        }

        return cnt;

    }

};

tiansuohaoer 10-25 11:55

6楼

BFS，遇到边界把贡献变0

class Solution {

public:

    vector<pair<int,int> > d{{0,1},{0,-1},{1,0},{-1,0}};

    int closedIsland(vector<vector<int>>& a) {

        int res=0,n=a.size(),m=a[0].size(),i,j,k;

        for(i=0;i<n;i++)for(j=0;j<m;j++)if(!a[i][j]){

            queue<pair<int,int> > q;

            k=1;

            q.push({i,j});

            while(!q.empty()){

                auto [x,y]=q.front();

                q.pop();

                for(auto [dx,dy]:d){

                    dx+=x; dy+=y;

                    if(dx<0||dx>=n||dy<0||dy>=m)k=0;

                    else if(!a[dx][dy]){

                        a[dx][dy]=1;

                        q.push({dx,dy});

                    }

                }

            }

            res+=k;

        }

        return res;

    }

};

Qiansui 10-25 13:55

7楼

DFS 判断陆地有没有触及边界捏

class Solution {

public:

    int closedIsland(vector<vector<int>>& grid) {

        int m = grid.size(), n = grid[0].size();

        vector vis(m, vector<bool>(n, false));



        int xm = 0, xn = 0, ym = 0, yn = 0;

        int fx[4] = {1, 0, -1, 0}, fy[4] = {0, 1, 0, -1};

        auto dfs = [&](this auto&& self, int x, int y) -> void {

            vis[x][y] = true;

            xm = max(xm, x);

            xn = min(xn, x);

            ym = max(ym, y);

            yn = min(yn, y);

            for(int i = 0; i < 4; ++ i){

                int xx = x + fx[i], yy = y + fy[i];

                if(xx < 0 || yy < 0 || xx >= m || yy >= n) continue;

                if(!vis[xx][yy] && grid[xx][yy] == 0)

                    self(xx, yy);

            }

        };



        int ans = 0;

        for(int i = 0; i < m; ++ i){

            for(int j = 0; j < n; ++ j){

                if(grid[i][j] == 0 && !vis[i][j]){

                    xm = xn = i;

                    ym = yn = j;

                    dfs(i, j);

                    if(xn > 0 && xm < m - 1 && yn > 0 && ym < n - 1) ++ ans;

                }

            }

        }

        return ans;

    }

};

宙读之魔术士 10-25 14:45

8楼

Kotlin每日打卡（DFS - 先反转网格外围上的0，接着处理里面的0）：

class Solution {

    companion object {

        val DIRS = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))

    }



    fun closedIsland(grid: Array<IntArray>): Int {

        val m = grid.size

        val n = grid[0].size

        if (m < 3 || n < 3) {

            return 0

        }

        fun dfs(x: Int, y: Int) {

            if (x !in 0..<m || y !in 0..<n || grid[x][y] != 0) {

                return

            }

            grid[x][y] = 1

            for ((dx, dy) in DIRS) {

                dfs(x + dx, y + dy)

            }

        }



        for (i in 0..<m) {

            val interval = if (i == 0 || i == (m - 1)) 1 else (n - 1)

            for (j in 0..<n step interval) {

                dfs(i, j)

            }

        }



        var ans = 0

        for (i in 1..<(m - 1)) {

            for (j in 1..<(n - 1)) {

                if (grid[i][j] != 0) {

                    continue

                }

                dfs(i, j)

                ans++

            }

        }

        return ans

    }

}

* 帖子来源Linux.do

附近帖子

飞读

魔法师

主题数
1

帖子数
1

注册排名
3

随机推荐