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;
}
};