1020. 飞地的数量

Alex_Shen
2022-03-29 / 0 评论 / 0 点赞 / 125 阅读 / 1,215 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-03-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1:

img

输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-enclaves
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
public:
    int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
    int numEnclaves(vector<vector<int>>& grid) {
        queue<pair<int,int>> q;
        int m=grid.size(),n=grid[0].size();
        for(int i=0;i<n;i++){
            if(grid[0][i]==1){
                q.push(pair<int,int>(0,i));
                grid[0][i]=0;
            }
            if(grid[m-1][i]){
                q.push(pair<int,int>(m-1,i));
                grid[m-1][i]=0;
            }
        }
        for(int i=1;i<m;i++){
            if(grid[i][0]==1){
                q.push(pair<int,int>(i,0));
                grid[i][0]=0;
            }
            if(grid[i][n-1]){
                q.push(pair<int,int>(i,n-1));
                grid[i][n-1]=0;
            }
        }
        while(!q.empty()){
            auto p=q.front();
            int x=p.first,y=p.second;
            // cout<<x<<' '<<y<<endl;
            for(int i=0;i<4;i++){
                int px=x+dir[i][0],py=y+dir[i][1];
                if(px>=0 && px<m && py>=0 && py<n){
                    if(grid[px][py]==1){
                        grid[px][py]=0;
                        q.push(pair<int,int>(px,py));
                    }
                }
            }
            q.pop();
        }
        int res=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1)
                    res++;
            }
        }
        return res;
    }
};
0

评论区