leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1970.cpp (1619B)

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