leetcode

0 // programming solution

1 class Solution {

2 static int seen[1001][1001];

3

4 static bool rec(int x, int y, int target, int a = 0, int b = 0) {

5 if (a + b == target) return true;

6 if (seen[a][b]) return false;

7 seen[a][b] = true;

8

9 const int leftx = x - a;

10 const int lefty = y - b;

11

12 if (rec(x, y, target, x, b)) return true;

13 if (rec(x, y, target, a, y)) return true;

14 if (rec(x, y, target, 0, b)) return true;

15 if (rec(x, y, target, a, 0)) return true;

16 if (rec(x, y, target, a - min(a, lefty), b + min(a, lefty))) return true;

17 if (rec(x, y, target, a + min(b, leftx), b - min(b, leftx))) return true;

18

19 return false;

20 }

21

22 public:

23 bool canMeasureWater(int x, int y, int target) const {

24 memset(seen, 0x00, sizeof(seen));

25 return rec(x, y, target);

26 }

27 };

28

29 int Solution::seen[1001][1001];

30

31 // Math solution: Bézout's identity

32 class Solution {

33 public:

34 bool canMeasureWater(int x, int y, int target) const {

35 if (x + y < target) return false;

36 if (x == target || y == target || x + y == target) return true;

37 return target % gcd(x, y) == 0;

38 }

39 };