algorithms

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

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