leetcode

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