LeetCode-Solutions/C++/minimum-xor-path-in-a-grid.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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// Time:  O(m * n * r), r = max(x for row in grid for x in row)
// Space: O(n * r / 64)

// dp, bitset
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        static const int MAX_LEN = 1024;

        vector<bitset<MAX_LEN>> dp(size(grid[0]));
        dp[0].set(0);
        for (int i = 0; i < size(grid); ++i) {
            vector<bitset<MAX_LEN>> new_dp(size(grid[0]));
            for (int j = 0; j < size(grid[0]); ++j) {
                for (int k = 0; k < MAX_LEN; ++k) {
                    if (dp[j][k] || (j - 1 >= 0 && new_dp[j - 1][k])) {
                        new_dp[j].set(k ^ grid[i][j]);
                    }
                }
            }
            dp = move(new_dp);
        }
        for (int i = 0; i < MAX_LEN; ++i) {
            if (dp.back()[i]) {
                return i;
            }
        }
        return -1;
    }
};

// Time:  O(m * n * r), r = max(x for row in grid for x in row)
// Space: O(n * r)
// dp
class Solution2 {
public:
    int minCost(vector<vector<int>>& grid) {
        uint32_t mx = 0;
        for (const auto& row : grid) {
            mx = max(mx, static_cast<uint32_t>(ranges::max(row)));
        }
        const auto& l = 1 << bit_width(mx);
        vector<vector<bool>> dp(size(grid[0]), vector<bool>(l));
        dp[0][0] = true;
        for (int i = 0; i < size(grid); ++i) {
            vector<vector<bool>> new_dp(size(grid[0]), vector<bool>(l));
            for (int j = 0; j < size(grid[0]); ++j) {
                for (int k = 0; k < l; ++k) {
                    if (dp[j][k] || (j - 1 >= 0 && new_dp[j - 1][k])) {
                        new_dp[j][k ^ grid[i][j]] = true;
                    }
                }
            }
            dp = move(new_dp);
        }
        for (int i = 0; i < l; ++i) {
            if (dp.back()[i]) {
                return i;
            }
        }
        return -1;
    }
};

// Time:  O(m * n * r), r = max(x for row in grid for x in row)
// Space: O(n * r)
// dp
class Solution_TLE {
public:
    int minCost(vector<vector<int>>& grid) {
        vector<unordered_set<int>> dp(size(grid[0]));
        dp[0].emplace(0);
        for (int i = 0; i < size(grid); ++i) {
            vector<unordered_set<int>> new_dp(size(grid[0]));
            for (int j = 0; j < size(grid[0]); ++j) {
                for (const auto& k : dp[j]) {
                    new_dp[j].emplace(k ^ grid[i][j]);
                }
                if (j - 1 < 0) {
                    continue;
                }
                for (const auto& k : new_dp[j - 1]) {
                    new_dp[j].emplace(k ^ grid[i][j]);
                }
            }
            dp = move(new_dp);
        }
        return ranges::min(dp.back());
    }
};