-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
73 lines (69 loc) · 1.69 KB
/
Solution.cs
File metadata and controls
73 lines (69 loc) · 1.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class Solution
{
public int LatestDayToCross(int row, int col, int[][] cells)
{
DSU dsu = new(row * col + 2);
int[][] grid = new int[row][];
for (int i = 0; i < row; i++)
{
grid[i] = new int[col];
}
int[] dirs = [1, 0, -1, 0, 1];
for (int i = cells.Length - 1; i >= 0; i--)
{
int r = cells[i][0] - 1;
int c = cells[i][1] - 1;
grid[r][c] = 1;
int id1 = r * col + c + 1;
for (int d = 0; d < 4; d++)
{
int nr = r + dirs[d];
int nc = c + dirs[d + 1];
if (nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] == 1)
{
dsu.Union(id1, nr * col + nc + 1);
}
}
if (r == 0) dsu.Union(0, id1);
if (r == row - 1) dsu.Union(row * col + 1, id1);
if (dsu.Find(0) == dsu.Find(row * col + 1)) return i;
}
return -1;
}
}
public class DSU
{
int[] root;
int[] size;
public DSU(int n)
{
root = new int[n];
size = new int[n];
for (int i = 0; i < n; i++)
{
root[i] = i;
size[i] = 1;
}
}
public int Find(int x)
{
if (root[x] != x)
{
root[x] = Find(root[x]);
}
return root[x];
}
public bool Union(int x, int y)
{
int rx = Find(x);
int ry = Find(y);
if (rx == ry) return false;
if (size[rx] > size[ry])
{
(rx, ry) = (ry, rx);
}
root[rx] = ry;
size[rx] += size[ry];
return true;
}
}