Advertisement
Guest User

Grokking 230

a guest
Aug 11th, 2022
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.88 KB | None | 0 0
  1. class Solution {
  2. private Map<String, Integer> memo = new HashMap<>();
  3.  
  4. public int minKnightMoves(int x, int y) {
  5. return dfs(Math.abs(x), Math.abs(y));
  6. }
  7.  
  8. private int dfs(int x, int y) {
  9. String memoKey = x + "|" + y;
  10. if (memo.containsKey(memoKey)) {
  11. return memo.get(memoKey);
  12. }
  13.  
  14. if (x + y == 0) {
  15. // Base case 1: Because x, y is positive, so when x + y == 0, both x and y is 0
  16. return 0;
  17. } else if (x + y == 2) {
  18. // Base case 2: If x + y == 2, Knight can reach destination in 2 steps
  19. return 2;
  20. } else {
  21. int ans = 1 + Math.min(dfs(Math.abs(x - 1), Math.abs(y - 2)),
  22. dfs(Math.abs(x - 2), Math.abs(y - 1)));
  23. memo.put(memoKey, ans);
  24. return ans;
  25. }
  26. }
  27. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement