Number of Enclaves（C++飞地的数量）

布满荆棘的人生 2023-01-16 06:49 83阅读 0赞

解题思路：

（1）bfs

class Solution {
    private:
        int count=0,tag=0,sum=0;
        vector<vector<int>> d={
       {-1,0},{1,0},{0,1},{0,-1}};
    public:
        void helper(vector<vector<int>>& g,vector<vector<int>> &v,int x,int y,int m,int n) {
            if(x==0 || x==m-1 || y==0 || y==n-1) tag=1;
            v[x][y]=1;
            count++;
            queue<pair<int,int>> q;
    
            for(int i=0;i<d.size();i++) {
                int x1=x+d[i][0];
                int y1=y+d[i][1];
                if(0<=x1 && x1<m && 0<=y1 && y1<n && v[x1][y1]==0 && g[x1][y1]==1) {
                    q.push({x1,y1});
                }
            }
    
            while(!q.empty()) {
                auto it=q.front();
                if(v[it.first][it.second]==0) helper(g,v,it.first,it.second,m,n);
                q.pop();
            }
            return;
        }
    
        int numEnclaves(vector<vector<int>>& g) {
            int m=g.size(),n=g[0].size();
            vector<vector<int>> v(m,vector<int>(n,0));
    
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    if(g[i][j]==1 && v[i][j]==0) {
                        tag=0,count=0;
                        helper(g,v,i,j,m,n);
                        if(tag==0) sum+=count;
                    }
                }
            }
            return sum;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，83人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_DFS_中等_1020.飞地的数量

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格

缺乏、安全感/ 2023年10月06日 22:32/ 0 赞/ 13 阅读

相关 LeetCode | 0200. Number of Islands岛屿数量【Python】

> LeetCode 0200. Number of Islands岛屿数量【Medium】【Python】【DFS】 Problem [LeetCode][] Gi

╰半夏微凉°/ 2023年07月09日 13:24/ 0 赞/ 19 阅读

相关 Leetcode DFS 1020. 飞地的数量

Leetcode DFS 1020. 飞地的数量 1、问题分析 2、问题解决 3、总结 1、问题分析具体思路是从边界出发标记连通块，标记完

约定不等于承诺〃/ 2023年03月14日 08:19/ 0 赞/ 8 阅读

相关 Number of Enclaves（C++飞地的数量）

解题思路：（1）bfs class Solution { private: int count=0,tag=0,sum=0;

布满荆棘的人生/ 2023年01月16日 06:49/ 0 赞/ 84 阅读

相关 leetcode 200. Number of Islands（岛屿的数量）

[https://leetcode.com/problems/number-of-islands/][https_leetcode.com_problems_number-of

小咪咪/ 2022年12月03日 09:17/ 0 赞/ 187 阅读

相关 Number of Provinces（C++省份数量）

解题思路：（1）dfs class Solution { public: void helper(vector<vector<int>>&

傷城~/ 2022年11月17日 10:25/ 0 赞/ 39 阅读

相关 leetcode 200. Number of Islands | 200. 岛屿数量（Java）

题目 [https://leetcode-cn.com/problems/number-of-islands/][https_leetcode-cn.com_proble

深碍√TFBOYSˉ_/ 2022年10月05日 05:46/ 0 赞/ 201 阅读

相关 Number of Islands（C++岛屿数量）

（1）dfs class Solution { private: vector<vector<int>> d={ {1,0

柔情只为你懂/ 2022年08月31日 01:52/ 0 赞/ 173 阅读

相关 [LeetCode] Number of Islands 岛屿的数量

![20181123213446581.png][] 测试数据: ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_a

旧城等待，/ 2022年04月14日 03:48/ 0 赞/ 191 阅读

相关 LeetCode-1020 飞地的数量（dfs）

给出一个二维数组 `A`，每个单元格为 0（代表海）或 1（代表陆地）。移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。返回网格中无法在任意

骑猪看日落/ 2022年02月21日 13:07/ 0 赞/ 98 阅读