Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- private Map<String, Integer> memo = new HashMap<>();
- public int minKnightMoves(int x, int y) {
- return dfs(Math.abs(x), Math.abs(y));
- }
- private int dfs(int x, int y) {
- String memoKey = x + "|" + y;
- if (memo.containsKey(memoKey)) {
- return memo.get(memoKey);
- }
- if (x + y == 0) {
- // Base case 1: Because x, y is positive, so when x + y == 0, both x and y is 0
- return 0;
- } else if (x + y == 2) {
- // Base case 2: If x + y == 2, Knight can reach destination in 2 steps
- return 2;
- } else {
- int ans = 1 + Math.min(dfs(Math.abs(x - 1), Math.abs(y - 2)),
- dfs(Math.abs(x - 2), Math.abs(y - 1)));
- memo.put(memoKey, ans);
- return ans;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement