# Pure algorithm solution, 36ms BFS.

• The straightforward BFS/DFS with state using both x and y will fail because of TLE or memory limit. The key is that we need different way to record state. Instead of using both[x][y], we actually need only one dimension array [w < max(x,y)]. In terms of algorithm design, this is a good example of how to reduce state space. It's pity that similar DFS solution gets 'run time error' due to the fairly small system stack limit.

``````bool canMeasureWaterbfs(int x, int y, int z) {
if(z > x+y || z < 0) return false;
if(z == 0) return true;
if(x < y) return canMeasureWaterbfs(y, x, z);
//assert x >= y
vector<char> visited(x+1, 0);
//bfs
queue<int> bfsQ;
bfsQ.push(x);
visited[x] = 1;
while(!bfsQ.empty()) {
int w = bfsQ.front();
bfsQ.pop();
if(w == z || w + y == z) return true;
if( w <= y) {
//water in Y
if(w + x == z) return true;
if(!visited[x - (y - w)]) {
bfsQ.push(x - (y - w));
visited[x - (y - w)] = 1;
}
}
//water in X
int diffX = x - w;
if(diffX >= y) {
if(!visited[w + y]) {
bfsQ.push(w+y);
visited[w + y] = 1;
}
}else {
if(!visited[y - diffX]) {
bfsQ.push(y - diffX);
visited[y - diffX] = 1;
}
}

}
return false;
}``````

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