leetcode

0 class Solution {

1 int n, m;

2 bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }

3

4 int flood_fill(vector<vector<int>> &grid, int x, int y) {

5 grid[x][y] = 0;

6 int count = 1;

7 if (valid(x + 1, y) && grid[x + 1][y]) count += flood_fill(grid, x + 1, y);

8 if (valid(x - 1, y) && grid[x - 1][y]) count += flood_fill(grid, x - 1, y);

9 if (valid(x, y + 1) && grid[x][y + 1]) count += flood_fill(grid, x, y + 1);

10 if (valid(x, y - 1) && grid[x][y - 1]) count += flood_fill(grid, x, y - 1);

11 return count;

12 }

13

14 public:

15 int numEnclaves(vector<vector<int>> &grid) {

16 n = grid.size(), m = grid[0].size();

17 for (int i = 0; i < n; i++) {

18 if (grid[i][0]) flood_fill(grid, i, 0);

19 if (grid[i][m - 1]) flood_fill(grid, i, m - 1);

20 }

21 for (int i = 0; i < m; i++) {

22 if (grid[0][i]) flood_fill(grid, 0, i);

23 if (grid[n - 1][i]) flood_fill(grid, n - 1, i);

24 }

25

26 int res = 0;

27 for (int i = 1; i < n - 1; i++) {

28 for (int j = 1; j < m - 1; j++) {

29 if (!grid[i][j]) continue;

30 res += flood_fill(grid, i, j);

31 }

32 }

33

34 return res;

35 }

36 };