making-a-large-island-v2.cpp (3003B)
1 class Solution { 2 public: 3 4 int sizeAtIfUnvisited(vector<vector<int>>& markedIslands,unordered_map<int,int>& componentSizes, int y, int x, std::vector<int>& visitedComps) { 5 if(y < markedIslands.size() && y >= 0 && x < markedIslands[0].size() && x >= 0) { 6 int islandNum = markedIslands[y][x]; 7 // find here with vector is faster than hashset. 8 if(std::find(visitedComps.begin(), visitedComps.end(), islandNum) == visitedComps.end()) { 9 visitedComps.push_back(islandNum); 10 return componentSizes[islandNum]; 11 } else { 12 return 0; 13 } 14 } else { 15 return 0; 16 } 17 } 18 19 int score(vector<vector<int>>& grid,vector<vector<int>>& markedIslands,unordered_map<int,int>& componentSizes,int y,int x) { 20 21 int sc = 0; 22 23 if(!grid[y][x]) { 24 sc += 1; 25 } 26 27 std::vector<int> visitedComps {}; 28 29 sc += sizeAtIfUnvisited(markedIslands, componentSizes, y, x, visitedComps); 30 sc += sizeAtIfUnvisited(markedIslands, componentSizes, y-1, x, visitedComps); 31 sc += sizeAtIfUnvisited(markedIslands, componentSizes, y+1, x, visitedComps); 32 sc += sizeAtIfUnvisited(markedIslands, componentSizes, y, x-1, visitedComps); 33 sc += sizeAtIfUnvisited(markedIslands, componentSizes, y, x+1, visitedComps); 34 35 return sc; 36 } 37 38 int dfs(vector<vector<int>>& grid, vector<vector<int>>& markedIslands, int mark, int x, int y) { 39 if( !(y < grid.size() && y >= 0 && x < grid[0].size() && x >= 0)) { 40 return 0; 41 } 42 if(markedIslands[y][x] != 0 || grid[y][x] == 0) { 43 return 0; 44 } 45 46 markedIslands[y][x] = mark; 47 int size = 1; 48 49 size += dfs(grid,markedIslands, mark, x + 1, y); 50 size += dfs(grid,markedIslands, mark, x - 1, y); 51 size += dfs(grid,markedIslands, mark, x, y + 1); 52 size += dfs(grid,markedIslands, mark, x, y - 1); 53 54 return size; 55 56 } 57 int largestIsland(vector<vector<int>>& grid) { 58 vector<vector<int>> markedIslands{}; 59 60 for(int x = 0; x < grid.size(); ++x) { 61 markedIslands.push_back(vector<int>(grid[x].size(),0)); 62 } 63 64 int components = 0; 65 unordered_map<int,int> componentSizes {}; 66 67 for(int y = 0; y < grid.size(); ++y) { 68 for(int x = 0; x < grid[y].size(); ++x) { 69 int sz = dfs(grid,markedIslands, components + 1, x, y); 70 if(sz > 0) { 71 componentSizes[components + 1] = sz; 72 components += 1; 73 } 74 } 75 } 76 77 int bestScore = 1; 78 79 for(int y = 0; y < grid.size(); ++y) { 80 for(int x = 0; x < grid[y].size(); ++x) { 81 int currentScore = score(grid,markedIslands,componentSizes,y,x); 82 bestScore = max(bestScore, currentScore); 83 } 84 } 85 86 return bestScore; 87 } 88 };