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