365.水壶问题 (Medium)*

题目描述*

有两个容量分别为 x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。

你允许：

装满任意一个水壶清空任意一个水壶从一个水壶向另外一个水壶倒水，直到装满或者倒空

代码*

数学问题，裴蜀定理，即：

$\forall a, b \in \mathbb{Z}, d = \gcd(a, b), \forall x, y \in \mathbb{Z} : \\ (ax + by) \mod d \equiv 0$

因此这道题转变为求解 x, y 的最大公因数，判断 z 是否是其整数倍。当然菜鸡虽然学过这个定理但是还是不会往这方面想的，还是用常规的做法吧。

在任意时刻，可以采取集中操作：填满 x 或 y，把 x 的水倒入 y，把 y 的水倒入 x，倒空 x 或 y。使用 dfs，记录 x 和 y 的当前水量，同时记录已搜索的状态。

遇到的小问题就是 unordered_set，底层是哈希表，而对 pair 并没有默认的哈希函数，所以要解决这个问题。

裴蜀定理dfs

class Solution {
private:
    int getGCD(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }
public:
    bool canMeasureWater(int x, int y, int z) {
        if(z == 0) {
            return true;
        }
        if(x + y < z) {
            return false;
        }
        return z % getGCD(x, y) == 0;
    }
};

using PII = pair<int, int>;

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        stack<PII> stk;
        stk.emplace(0, 0);
        auto hash_function = [](const PII& o) {return hash<int>()(o.first) ^ hash<int>()(o.second);};
        unordered_set<PII, decltype(hash_function)> seen(0, hash_function);
        while (!stk.empty()) {
            if (seen.count(stk.top())) {
                stk.pop();
                continue;
            }
            seen.emplace(stk.top());

            auto [remain_x, remain_y] = stk.top();
            stk.pop();
            if (remain_x == z || remain_y == z || remain_x + remain_y == z) {
                return true;
            }
            // 把 X 壶灌满。
            stk.emplace(x, remain_y);
            // 把 Y 壶灌满。
            stk.emplace(remain_x, y);
            // 把 X 壶倒空。
            stk.emplace(0, remain_y);
            // 把 Y 壶倒空。
            stk.emplace(remain_x, 0);
            // 把 X 壶的水灌进 Y 壶，直至灌满或倒空。
            stk.emplace(remain_x - min(remain_x, y - remain_y), remain_y + min(remain_x, y - remain_y));
            // 把 Y 壶的水灌进 X 壶，直至灌满或倒空。
            stk.emplace(remain_x + min(remain_y, x - remain_x), remain_y - min(remain_y, x - remain_x));
        }
        return false;
    }
};

最后更新: July 23, 2022