leecode 水壶问题
有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升 水。
你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空
求倒的顺序
const reslujing = [];
const map2 = {};
var getlujing = function (r, map1) {
var key = r[0] + '-' + r[1];
while (key && map1[key]) {
reslujing.push(key)
map2[key] = 1;
var kkk = key;
key = ''
for (var i = 0; map1[kkk] && i < map1[kkk].length; i++) {
var keytem = map1[kkk] && map1[kkk][i];
if (!map2[keytem]) {
key = keytem;
break;
}
}
// console.log('======================')
}
}
/**
* @param {number} x
* @param {number} y
* @param {number} z
* @return {boolean}
*/
var canMeasureWater = function (x, y, z) {
var stack = [];
var map = {};
var map1 = {};
if (!z) {
return true;
}
if (!x || !y) {
return x + y == z;
}
var first = [0, 0]
stack.push(first)
while (Object.keys(stack).length) {
var r = stack.pop();
if (r[0] == z || r[1] == z || r[0] + r[1] == z) {
getlujing(r, map1)
return true;
}
map[r[0] + '' + r[1]] = 1;
// 把 X 壶的水灌进 Y 壶，直至灌满或倒空；
var a = r[0] - Math.min(r[0], y - r[1]);
var b = r[1] + Math.min(r[0], y - r[1]);
if (!map[a + '' + b]) {
stack.push([a, b])
map1[a + '-' + b] = map1[a + '-' + b] || [];
map1[a + '-' + b].push(r[0] + '-' + r[1])
}
// 把 Y 壶的水灌进 X 壶，直至灌满或倒空；
a = r[0] + Math.min(r[1], x - r[0]);
b = r[1] - Math.min(r[1], x - r[0]);
if (!map[a + '' + b]) {
stack.push([a, b])
map1[a + '-' + b] = map1[a + '-' + b] || [];
map1[a + '-' + b].push(r[0] + '-' + r[1])
}
// 把 x 倒满；
a = x
b = r[1]
if (!map[a + '' + b]) {
stack.push([a, b])
map1[a + '-' + b] = map1[a + '-' + b] || [];
map1[a + '-' + b].push(r[0] + '-' + r[1])
}
// y full；
a = r[0]
b = y
if (!map[a + '' + b]) {
stack.push([a, b])
map1[a + '-' + b] = map1[a + '-' + b] || [];
map1[a + '-' + b].push(r[0] + '-' + r[1])
}
// a empty；
a = 0;
b = r[1];
if (!map[a + '' + b]) {
stack.push([a, b])
map1[a + '-' + b] = map1[a + '-' + b] || [];
map1[a + '-' + b].push(r[0] + '-' + r[1])
}
// 把 Y 壶的水灌进 X 壶，直至灌满或倒空；
a = r[0];
b = 0;
if (!map[a + '' + b]) {
stack.push([a, b])
map1[a + '-' + b] = map1[a + '-' + b] || [];
map1[a + '-' + b].push(r[0] + '-' + r[1])
}
}
return false
};
var j = canMeasureWater(3, 5, 4)
if (j) console.log(JSON.stringify(reslujing.reverse()))
