讨论/题目交流/🏆 第 162 场力扣周赛/
🏆 第 162 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 奇数值单元格的数目
4 分 - 重构 2 行二进制矩阵
5 分 - 统计封闭岛屿的数目
6 分 - 得分最高的单词集合

展开讨论

第三题 在内圈开始dfs 如果从某点出发 到达过边界的陆地 则此次dfs形成的联通块必不被水包围 判定为 0 不计入答案

class Solution {
public:
    int n,m,dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
    void dfs(vector<vector<int>>& g, int x, int y, int &flag){
        g[x][y] = 1;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&!g[nx][ny]){//合法位置
                if(nx==0||ny==0||nx==n-1||ny==m-1) flag = 0;//搜到了边界处的陆地 则这一片不被水包围
                dfs(g,nx,ny,flag);
            }
        }
    }
    int closedIsland(vector<vector<int>>& g) {
        int sum = 0,flag;
        n = g.size(), m = g[0].size();//无需再定义,这里注意是全局变量(⊙o⊙)…
        for(int i = 1; i < n-1; i++)//边界点必定不计入答案 所以从内侧的点开始搜索
            for(int j = 1; j < m-1; j++)
                if(!g[i][j]) flag = 1, dfs(g,i,j,flag), sum += flag;//从i,j出发是否可以碰到边界 假设碰不到flag=1 
        return sum;
    }
};
1
展开全部 22 讨论