algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

number-of-closed-islands.cpp (1483B)


      1 int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited,int y, int x) {
      2     
      3     if(!(y >= 0 && y < visited.size() && x < visited[0].size() && x >= 0)) {
      4         return -1; // out of bounds, means borders edge
      5     }
      6 
      7     if(visited[y][x] || grid[y][x] == 1) {
      8         return 0;
      9     }
     10 
     11     visited[y][x] = true;
     12 
     13     int res = 0;
     14 
     15     res = min(res,dfs(grid,visited,y-1,x));
     16     res = min(res,dfs(grid,visited,y,x-1));
     17     res = min(res,dfs(grid,visited,y+1,x));
     18     res = min(res,dfs(grid,visited,y,x+1));
     19 
     20     if(res == 0) {
     21         return 1;
     22     }
     23 
     24     return res;
     25 }
     26 
     27 class Solution {
     28 public:
     29     int closedIsland(vector<vector<int>>& grid) {
     30         // for each position:
     31             // perform dfs for the island
     32             // if the island borders an edge, don't count it
     33             // return count of islands
     34 
     35             vector<vector<bool>> visited {};
     36 
     37             for(int i = 0; i < grid.size(); ++i) {
     38                 visited.emplace_back(vector<bool> (grid[i].size(), false));
     39             }
     40 
     41             int res = 0;
     42 
     43             for(int y = 0; y < grid.size(); ++y) {
     44                 for(int x = 0; x < grid[y].size(); ++x) {
     45                     if(grid[y][x] == 0 && !visited[y][x]) {
     46                         int re = dfs(grid, visited, y, x);
     47                         if(re == 1) {
     48                             res += 1;                        
     49                         }
     50                     }
     51                 }
     52             }
     53 
     54             return res;
     55     }
     56 };