0365.cpp (1188B)
1 // programming solution 2 class Solution { 3 static int seen[1001][1001]; 4 5 static bool rec(int x, int y, int target, int a = 0, int b = 0) { 6 if (a + b == target) return true; 7 if (seen[a][b]) return false; 8 seen[a][b] = true; 9 10 const int leftx = x - a; 11 const int lefty = y - b; 12 13 if (rec(x, y, target, x, b)) return true; 14 if (rec(x, y, target, a, y)) return true; 15 if (rec(x, y, target, 0, b)) return true; 16 if (rec(x, y, target, a, 0)) return true; 17 if (rec(x, y, target, a - min(a, lefty), b + min(a, lefty))) return true; 18 if (rec(x, y, target, a + min(b, leftx), b - min(b, leftx))) return true; 19 20 return false; 21 } 22 23 public: 24 bool canMeasureWater(int x, int y, int target) const { 25 memset(seen, 0x00, sizeof(seen)); 26 return rec(x, y, target); 27 } 28 }; 29 30 int Solution::seen[1001][1001]; 31 32 // Math solution: Bézout's identity 33 class Solution { 34 public: 35 bool canMeasureWater(int x, int y, int target) const { 36 if (x + y < target) return false; 37 if (x == target || y == target || x + y == target) return true; 38 return target % gcd(x, y) == 0; 39 } 40 };