<p>You are given two jugs with capacities <code>x</code> liters and <code>y</code> liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach <code>target</code> using the following operations:</p>

<ul>
	<li>Fill either jug completely with water.</li>
	<li>Completely empty either jug.</li>
	<li>Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> x = 3, y = 5, target = 4 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> true </span></p>

<p><strong>Explanation:</strong></p>

<p>Follow these steps to reach a total of 4 liters:</p>

<ol>
	<li>Fill the 5-liter jug (0, 5).</li>
	<li>Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).</li>
	<li>Empty the 3-liter jug (0, 2).</li>
	<li>Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).</li>
	<li>Fill the 5-liter jug again (2, 5).</li>
	<li>Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).</li>
	<li>Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).</li>
</ol>

<p>Reference: The <a href="https://www.youtube.com/watch?v=BVtQNK_ZUJg&amp;ab_channel=notnek01" target="_blank">Die Hard</a> example.</p>
</div>

<p><strong class="example">Example 2: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> x = 2, y = 6, target = 5 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> false </span></p>
</div>

<p><strong class="example">Example 3: </strong></p>

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
<p><strong>Input: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> x = 1, y = 2, target = 3 </span></p>

<p><strong>Output: </strong> <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> true </span></p>

<p><strong>Explanation:</strong> Fill both jugs. The total amount of water in both jugs is equal to 3 now.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= x, y, target&nbsp;&lt;= 10<sup>3</sup></code></li>
</ul>

class Solution {
public:
    // pair<int, int> fill_x(int x, int y, int x1, int y1){
    //     return {x, y1};
    // }
    // pair<int, int> fill_y(int x, int y, int x1, int y1){
    //     return {x1, y};
    // }
    // pair<int, int> pour_x(int x, int y, int x1, int y1){
    //     return {0, y1};
    // }
    // pair<int, int> pour_y(int x, int y, int x1, int y1){
    //     return {x, 0};
    // }
    // pair<int, int> x_to_y(int x, int y, int x1, int y1){
    //     int amount = min(x1, y - y1);
    //     return {x1 - amount, y1 + amount};
    // }
    // pair<int, int> y_to_x(int x, int y, int x1, int y1){
    //     int amount = min(x - x1, y1);
    //     return {x1 + amount, y1 - amount};
    // }
    bool canMeasureWater(int x, int y, int target) {
        if(x == target || y == target || x + y == target) return true;
        queue<pair<int, int>> q;
        q.push({0, 0});
        unordered_set<string> visited;
        while(!q.empty()){
            pair<int, int> cur = q.front();
            q.pop();
            int x1 = cur.first;
            int y1 = cur.second;
            string key = to_string(x1) + "-" + to_string(y1);
            if(visited.count(key) > 0) continue;
            visited.insert(key);
            if(x1 == target || y1 == target || x1 + y1 == target) return true;
            q.push({x, y1});
            q.push({x1, y});
            q.push({0, y1});
            q.push({x, 0});
            int amount = min(x1, y - y1);;
            q.push({x1 - amount, y1 + amount});
            amount = min(x - x1, y1);
            q.push({x1 + amount, y1 - amount});
        }
        return false;
    }
};

// class Solution {
// public:
//     vector<int> results;
//     //vector<int> checked;
//     void pour(int x, int y, int diff){
//         //if(diff < x){
//         diff = x - diff;
//         //checked.push_back(diff);
//         diff = y - diff;
        
//         cout<<diff<<endl;
//         if(find(results.begin(), results.end(), diff) == results.end()){
//             results.push_back(diff);
//             pour(x, y, diff % x);
//         }
        
//         // }
//         // else{
//         //     results.push_back(diff - x);
//         // }
//     }
//     bool canMeasureWater(int x, int y, int target) {
//         if(x > y){
//             int tmp = x;
//             x = y;
//             y = tmp;
//         }
//         if(x == target || y == target || x + y == target || y - x == target) return true;
//         else{
//             results.push_back(x);
//             results.push_back(y);
//             results.push_back(x + y);
//             for(int i = 1; i <= y / x; i++) results.push_back(y - x * i);
//             pour(x, y, y % x);
//             if(find(results.begin(), results.end(), target) != results.end() || find(results.begin(), results.end(), target - x) != results.end() || find(results.begin(), results.end(), target - y) != results.end() || find(results.begin(), results.end(), x - target) != results.end() || find(results.begin(), results.end(), y - target) != results.end()) return true;
//             else return false;
//         }
        
//     }
// };
10200