leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1970.cpp (1619B)

      1 class UnionFind {
      2     int root[20002], size[20002];
      3 
      4   public:
      5     UnionFind() {
      6         for (int i = 0; i < 20002; i++) {
      7             root[i] = i;
      8             size[i] = 1;
      9         }
     10     }
     11 
     12     int find(int x) {
     13         while (x != root[x])
     14             x = root[x] = root[root[x]];
     15         return x;
     16     }
     17 
     18     void join(int x, int y) {
     19         x = find(x), y = find(y);
     20         if (x != y) {
     21             if (size[x] > size[y]) swap(x, y);
     22             root[x] = y;
     23             size[y] += size[x];
     24         }
     25     }
     26 
     27     bool connected(int x, int y) { return find(x) == find(y); }
     28 };
     29 
     30 class Solution {
     31     int grid[20000] = {0};
     32 
     33   public:
     34     int latestDayToCross(int row, int col, const vector<vector<int>> &cells) {
     35         static const auto index = [&](int i, int j) { return i * col + j; };
     36         static const auto valid = [&](int i, int j) { return i >= 0 && j >= 0 && i < row && j < col; };
     37         static const int offset_x[] = {0, 0, 1, -1};
     38         static const int offset_y[] = {1, -1, 0, 0};
     39 
     40         UnionFind uf;
     41 
     42         for (int i = cells.size() - 1; i >= 0; i--) {
     43             const int x = cells[i][0] - 1, y = cells[i][1] - 1, ind = index(x, y);
     44             grid[ind] = true;
     45 
     46             for (int k = 0; k < 4; k++) {
     47                 int i = x + offset_x[k], j = y + offset_y[k];
     48                 if (!valid(i, j) || !grid[index(i, j)]) continue;
     49                 uf.join(ind, index(i, j));
     50             }
     51 
     52             if (x == 0) uf.join(ind, 20000);
     53             if (x == row - 1) uf.join(ind, 20001);
     54             if (uf.connected(20000, 20001)) return i;
     55         }
     56 
     57         return row * col;
     58     }
     59 };