nikunjsoni

1970

Aug 15th, 2021
981
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Union Find solution
  2. TC: O(r*c*An)
  3.  
  4. class UF{
  5. private:
  6.     vector<int> parent, rank;
  7.  
  8. public:
  9.     UF(int n){
  10.         parent.resize(n+1);
  11.         for(int i=0; i<=n; i++)
  12.             parent[i] = i;
  13.         rank.resize(n+1, 0);
  14.     }
  15.  
  16.     int find(int x){
  17.         if(parent[x] == x) return x;
  18.         return parent[x] = find(parent[x]);
  19.     }
  20.    
  21.     void unionSet(int x, int y){
  22.         int px = find(x);
  23.         int py = find(y);
  24.         if(px != py){
  25.             if(rank[px] > rank[py]){
  26.                 parent[py] = px;
  27.             }
  28.             else{
  29.                 parent[px] = py;
  30.                 if(rank[px] == rank[py])
  31.                     rank[py]++;
  32.             }
  33.         }
  34.     }
  35. };
  36.  
  37. class Solution {
  38. public:
  39.     int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
  40.         int n=(row+1)*(col+1);
  41.         int grid[row+1][col+1];
  42.         memset(grid, 0, sizeof grid);
  43.        
  44.         UF uf = UF(n);
  45.         for(int i=1; i<col; i++){
  46.             uf.unionSet(get_hash(1, i, col), get_hash(1, i+1, col));
  47.             if(row > 1)
  48.             uf.unionSet(get_hash(row, i, col), get_hash(row, i+1, col));
  49.         }
  50.        
  51.         // Get the last state.
  52.         int dx[4] = {1, 0, 0, -1};
  53.         int dy[4] = {0, -1, 1, 0};
  54.         for(auto vec: cells){
  55.             grid[vec[0]][vec[1]] = 1;
  56.         }
  57.        
  58.         // Make graph.
  59.         for(int i=1; i<=row; i++){
  60.             for(int j=1; j<=col; j++){
  61.                 if(grid[i][j]) continue;
  62.                 for(int k=0; k<4; k++){
  63.                     int nextR = i+dx[k], nextC = j+dy[k];
  64.                     if(valid(nextR, nextC, row, col) && grid[nextR][nextC] == 0){
  65.                         if(i==1 && k==0)
  66.                             uf.unionSet(get_hash(nextR, nextC, col), get_hash(i, j, col));
  67.                         if(i != 1){
  68.                             if(i==row && k==3){
  69.                                 uf.unionSet(get_hash(nextR, nextC, col), get_hash(i, j, col));
  70.                             }
  71.                             else if(i != row){
  72.                                 uf.unionSet(get_hash(nextR, nextC, col), get_hash(i, j, col));
  73.                             }
  74.                         }
  75.                     }
  76.                 }
  77.             }
  78.         }
  79.        
  80.         int day = cells.size();
  81.         int firstRowSet=0, lastRowSet=0;
  82.         for(int i=1; i<=col; i++){
  83.             if(grid[1][i] == 0) firstRowSet = 1;
  84.             if(grid[row][i] == 0) lastRowSet = 1;
  85.         }
  86.        
  87.         // Get the last day.
  88.         while(day>0){
  89.             if(firstRowSet && lastRowSet){
  90.                 int px = uf.find(get_hash(1,1,col));
  91.                 int py = uf.find(get_hash(row,1,col));
  92.                 if(px == py)
  93.                     return day;
  94.             }
  95.             day--;
  96.             int r=cells[day][0], c=cells[day][1];
  97.             if(r == 1) firstRowSet = 1;
  98.             if(r == row) lastRowSet = 1;
  99.             grid[r][c] = 0;
  100.             for(int k=0; k<4; k++){
  101.                 int nextR = r+dx[k], nextC = c+dy[k];
  102.                 if(valid(nextR, nextC, row, col) && grid[nextR][nextC] == 0){
  103.                     uf.unionSet(get_hash(nextR, nextC, col), get_hash(r, c, col));
  104.                 }
  105.             }
  106.         }
  107.         return 0;
  108.     }
  109.    
  110.     int get_hash(int r, int c, int cols){
  111.         return r*cols+c;
  112.     }
  113.    
  114.     int valid(int r, int c, int row, int col){
  115.         if(r>=1 && r<=row && c>=1 && c<=col) return true;
  116.         return false;
  117.     }
  118.    
  119. };
  120.  
  121. ----------------------
  122. Binary Search Solution
  123. TC: O(r*c*logn)
  124.  
  125. class Solution {
  126. public:
  127.     int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
  128.         int left = 1, right = cells.size(), ans = 0;
  129.         while (left <= right) {
  130.             int mid = left + (right - left) / 2;
  131.             if (canWalk(cells, row, col, mid)) {
  132.                 ans = mid; // Update current answer so far
  133.                 left = mid + 1; // Try to find a larger day
  134.             } else right = mid - 1; // Try to find a smaller day
  135.         }
  136.         return ans;
  137.     }
  138.     int DIR[5] = {0, 1, 0, -1, 0};
  139.     bool canWalk(vector<vector<int>>& cells, int row, int col, int dayAt) {
  140.         vector<vector<bool>> grid(row, vector<bool>(col, 0)); // Create grid in the `dayAt` th date
  141.         for (int i = 0; i < dayAt; ++i) grid[cells[i][0]-1][cells[i][1]-1] = 1;
  142.         queue<pair<int, int>> bfs;
  143.         for (int c = 0; c < col; ++c) {
  144.             if (grid[0][c] == 0) { // Add all valid start cells in the top row
  145.                 bfs.push({0, c});
  146.                 grid[0][c] = 1; // Mark as visited
  147.             }
  148.         }
  149.         while (!bfs.empty()) {
  150.             auto [r, c] = bfs.front(); bfs.pop();
  151.             if (r == row - 1) return true; // Reach to bottom -> Return Valid
  152.             for (int i = 0; i < 4; ++i) {
  153.                 int nr = r + DIR[i], nc = c + DIR[i+1];
  154.                 if (nr < 0 || nr == row || nc < 0 || nc == col || grid[nr][nc] == 1) continue;
  155.                 grid[nr][nc] = 1; // Mark as visited
  156.                 bfs.push({nr, nc});
  157.             }
  158.         }
  159.         return false;
  160.     }
  161. };
RAW Paste Data