Posted on

Description

Submission

class Solution {
    int m, n;
    vector<vector<int>> visited;
    int cnt;
    bool isValid;
    static constexpr int dirs[] = {-1, 0, 1, 0, -1};

    void dfs(int x, int y, vector<vector<int>>& grid) {
        if(visited[x][y]) return;
        visited[x][y] = 1;
        ++cnt;

        for(int i = 0; i < 4; ++i) {
            int x1 = x + dirs[i];
            int y1 = y + dirs[i+1];

            if(x1 < 0 || y1 < 0 || x1 >= m || y1 >= n) {
                isValid = false;
                continue;
            }

            if(visited[x1][y1] || !grid[x1][y1]) continue;

            dfs(x1, y1, grid);
        }
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        visited.resize(m, vector<int>(n, 0));

        int ret = 0;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(!grid[i][j] || visited[i][j]) continue;
                cnt = 0;
                isValid = true;
                dfs(i, j, grid);

                if(isValid) ret += cnt;
            }
        }

        return ret;
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *