leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1020.cpp (1260B)

      1 class Solution {
      2     int n, m;
      3     bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
      4 
      5     int flood_fill(vector<vector<int>> &grid, int x, int y) {
      6         grid[x][y] = 0;
      7         int count = 1;
      8         if (valid(x + 1, y) && grid[x + 1][y]) count += flood_fill(grid, x + 1, y);
      9         if (valid(x - 1, y) && grid[x - 1][y]) count += flood_fill(grid, x - 1, y);
     10         if (valid(x, y + 1) && grid[x][y + 1]) count += flood_fill(grid, x, y + 1);
     11         if (valid(x, y - 1) && grid[x][y - 1]) count += flood_fill(grid, x, y - 1);
     12         return count;
     13     }
     14 
     15   public:
     16     int numEnclaves(vector<vector<int>> &grid) {
     17         n = grid.size(), m = grid[0].size();
     18         for (int i = 0; i < n; i++) {
     19             if (grid[i][0]) flood_fill(grid, i, 0);
     20             if (grid[i][m - 1]) flood_fill(grid, i, m - 1);
     21         }
     22         for (int i = 0; i < m; i++) {
     23             if (grid[0][i]) flood_fill(grid, 0, i);
     24             if (grid[n - 1][i]) flood_fill(grid, n - 1, i);
     25         }
     26 
     27         int res = 0;
     28         for (int i = 1; i < n - 1; i++) {
     29             for (int j = 1; j < m - 1; j++) {
     30                 if (!grid[i][j]) continue;
     31                 res += flood_fill(grid, i, j);
     32             }
     33         }
     34 
     35         return res;
     36     }
     37 };