C++, hash table solution.


  • 0

    The gcd math solution is very cool. However, here I'm providing a pure coder's solution. Just for reference.

    bool canMeasureWater(int x, int y, int z) {
       // cout<<INT_MAX;
        if (z<0 || z>x+y) return false;
        vector<int> flag(x+y+1,0);
        flag[0]=1;
        queue<int> canReach;
        canReach.push(0);
        while (!canReach.empty()){
            int k=canReach.front();
            canReach.pop();
            if (k+x==z || k+y==z || k-x==z || k-y==z || x-y+k==z || y-x+k==z) return true;
            if (k+x>=0 && k+x<=x+y && flag[k+x]==0){
                flag[k+x] = 1;
                canReach.push(k+x);
            }
            if (k-y>=0 && k-y<=x+y && flag[k-y]==0){
                flag[k-y] = 1;
                canReach.push(k-y);
            }
            if (k+y>=0 && k+y<=x+y && flag[k+y]==0){
                flag[k+y] = 1;
                canReach.push(k+y);
            }
            if (k-x>=0 && k-x<=x+y && flag[k-x]==0){
                flag[k-x] = 1;
                canReach.push(k-x);
            }
            if (x-y+k>=0 && x-y+k<=x+y && flag[x-y+k]==0){
                flag[x-y+k] = 1;
                canReach.push(x-y+k);
            }
            if (y-x+k>=0 && y-x+k<=x+y && flag[y-x+k]==0){
                flag[y-x+k] = 1;
                canReach.push(y-x+k);
            }
        }
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.