making-a-large-island.cpp (3091B)
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({}); 62 for(int y = 0; y < grid[x].size(); ++y) { 63 markedIslands[x].push_back(0); 64 } 65 } 66 67 int components = 0; 68 unordered_map<int,int> componentSizes {}; 69 70 for(int y = 0; y < grid.size(); ++y) { 71 for(int x = 0; x < grid[y].size(); ++x) { 72 int sz = dfs(grid,markedIslands, components + 1, x, y); 73 if(sz > 0) { 74 componentSizes[components + 1] = sz; 75 components += 1; 76 } 77 } 78 } 79 80 int bestScore = 1; 81 82 for(int y = 0; y < grid.size(); ++y) { 83 for(int x = 0; x < grid[y].size(); ++x) { 84 int currentScore = score(grid,markedIslands,componentSizes,y,x); 85 bestScore = max(bestScore, currentScore); 86 } 87 } 88 89 return bestScore; 90 } 91 };