1970. Last Day Where You Can Still Cross

https://leetcode.com/problems/last-day-where-you-can-still-cross/

對總共的天數進行 binary search，然後使用 dfs 來看是否能夠從最上面走到最下面。

這邊的 update 是看 cur(當前的 grid 更新到第幾天) 跟 mid。如果 cur < mid，代表需要更新到第 mid 天，因此把 grid 變成 -1。反過來的話則是把 grid 變成 0。
dfs 中，把走過的 grid 變成 mid，因此遇到 mid 或是 -1 的時候，代表無法再走下去了。

 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
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
    vector<vector<int>> grid(row, vector<int> (col, 0));
    int cur = 0;
    int l = 1, r = row * col;
    while (l < r){
        int mid = r - (r - l) / 2;
        update(cur, mid, grid, cells);
        if (possible(mid, grid, row, col)){
            l = mid;
        }
        else {
            r = mid - 1;
        }
    }
    return l;
}

void update(int &cur, int mid, vector<vector<int>> &grid, vector<vector<int>>& cells){
    if (cur < mid){
        for (int i = cur + 1; i <= mid; i++){
            int row_update = cells[i - 1][0] - 1;
            int col_update = cells[i - 1][1] - 1;
            grid[row_update][col_update] = -1;
        }
    }
    else {
        for (int i = cur; i > mid; i--){
            int row_update = cells[i - 1][0] - 1;
            int col_update = cells[i - 1][1] - 1;
            grid[row_update][col_update] = 0;
        }
    }
    cur = mid;
    return;
}

bool possible(int mid, vector<vector<int>> &grid, int rows, int cols){
    stack<pair<int, int>> stk;
    for (int i = 0; i < cols; i++){
        if (grid[0][i] != -1){
            stk.push({0, i});
        }
    }
    while (not stk.empty()){
        auto [row, col] = stk.top();
        stk.pop();
        if (row == rows - 1){
            return true;
        }
        int dirc[] = {0, -1, 0, 1, 0};
        for (int i = 0; i < 4; i++){
            int r = row + dirc[i];
            int c = col + dirc[i + 1];
            if (r < 0 || r >= rows || c < 0 || c >= cols){
                continue;
            }
            if (grid[r][c] == mid || grid[r][c] == -1){
                continue;
            }
            stk.push({r, c});
            grid[r][c] = mid;
        }
    }
    return false;
}

time complexity: $O(\log(row \times col) \times row \times col)$
space complextiy: $O(row \times col)$
其中 update 的複雜度會是 $O(row \times col)$，因為每一次只會更新 binary search range 的一半，會是 $(row \times col) \sum_{k = 1}^{\log(row \times col)}\frac{1}{2^k} = row \times col$。

另一個解法是 disjoint set。
從最後一天往前看，看什麼時候可以從最上面走到最下面。
特別注意的是，這邊多建立了兩個 node，分別代表最上面一排跟最下面一排。
每一天的最後只需要檢查最上面的一列跟最下面的一列有沒有一樣的 parent，有的話，就代表可以從最上面走到最下面。
為了快速檢查這件事情，把第一列的 node 都連到 n，最後一列連到 n + 1，這樣只需要看 find(parent, n) == find(parent, n + 1) 即可。

 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
int find(vector<int> &parent, int x){
    if (parent[x] != x){
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}
void uni(vector<int> &parent, int x, int y){
    int p_x = find(parent, x);
    int p_y = find(parent, y);
    if (p_x != p_y){
        parent[p_x] = p_y;
    }
    return;
}
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
    int n = cells.size();
    vector<vector<int>> grid(row, vector<int> (col, 1));
    vector<int> parent(n + 2);
    for (int i = 0; i < n + 2; i++){
        parent[i] = i;
    }
    for (int i = n - 1; i >= 0; i--){
        int cur_row = cells[i][0] - 1;
        int cur_col = cells[i][1] - 1;
        int cur_index = cur_row * col + cur_col;
        grid[cur_row][cur_col] = 0;
        if (cur_row == 0){
            uni(parent, cur_index, n);
        }
        else if (cur_row == row - 1){
            uni(parent, cur_index, n + 1);
        }
        int dirc[] = {0, -1, 0, 1, 0};
        for (int j = 0; j < 4; j++){
            int next_row = cur_row + dirc[j];
            int next_col = cur_col + dirc[j + 1];
            if (next_row < 0 || next_row >= row || next_col < 0 || next_col >= col){
                continue;
            }
            if (grid[next_row][next_col] == 1){
                continue;
            }
            int next_index = next_row * col + next_col;
            uni(parent, cur_index, next_index);
        }
        if (find(parent, n) == find(parent, n + 1)){
            return i;
        }
    }
    return -1;
}

time complexity: $O(row \times col)$
space complextiy: $O(row \times col)$