LeetCode-Solutions/C++/multi-source-flood-fill.cpp at master · kamyu104/LeetCode-Solutions · GitHub

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
74
75
76
// Time:  O(n * m)
// Space: O(n * m)

// bfs, flood fill
class Solution {
public:
    vector<vector<int>> colorGrid(int n, int m, vector<vector<int>>& sources) {
        static const vector<pair<int, int>>& DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        vector<vector<int>> result(n, vector<int>(m));
        vector<pair<int, int>> q;
        for (const auto& x : sources) {
            const auto& r = x[0], &c = x[1], &color = x[2];
            result[r][c] = color;
            q.emplace_back(r, c);
        }
        while (!empty(q)) {
            vector<pair<int, int>> new_q;
            for (const auto& [r, c] : q) {
                for (const auto& [dr, dc] : DIRECTIONS) {
                    const auto& nr = r + dr, &nc = c + dc;
                    if (!(0 <= nr && nr < n && 0 <= nc && nc < m)) {
                        continue;
                    }
                    if (result[nr][nc] == 0) {
                        result[nr][nc] = -result[r][c];
                        new_q.emplace_back(nr, nc);
                    } else if (result[nr][nc] < 0) {
                        result[nr][nc] = min(result[nr][nc], -result[r][c]);
                    }
                }
            }
            for (const auto& [nr, nc] : new_q) {
                result[nr][nc] = -result[nr][nc];
            }
            q = move(new_q);
        }
        return result;
    }
};

// Time:  O(slogs + n * m) = O((n * m) * log(n * m))
// Space: O(n * m)
// sort, bfs, flood fill
class Solution2 {
public:
    vector<vector<int>> colorGrid(int n, int m, vector<vector<int>>& sources) {
        static const vector<pair<int, int>>& DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        ranges::sort(sources, [](const auto& a, const auto& b) {
            return a[2] > b[2];
        });
        vector<vector<int>> result(n, vector<int>(m));
        vector<pair<int, int>> q;
        for (const auto& x : sources) {
            const auto& r = x[0], &c = x[1], &color = x[2];
            result[r][c] = color;
            q.emplace_back(r, c);
        }
        while (!empty(q)) {
            vector<pair<int, int>> new_q;
            for (const auto& [r, c] : q) {
                for (const auto& [dr, dc] : DIRECTIONS) {
                    const auto& nr = r + dr, &nc = c + dc;
                    if (!(0 <= nr && nr < n && 0 <= nc && nc < m && result[nr][nc] == 0)) {
                        continue;
                    }
                    result[nr][nc] = result[r][c];
                    new_q.emplace_back(nr, nc);
                }
            }
            q = move(new_q);
        }
        return result;
    }
};