This doesn’t make test case 3 correct. I’d love to see the knight moving from (0, 0) to (1, 1) in 2 moves (assuming imaginary coordinates are not allowed?)
Test case 3: can you show the knight moving from (0, 0) to (1, 1) in 2 moves without using complex numbers?
LOL, negative coords are allowed. 
Why is hash used in C++ and Java solutions?
Would it not be [0,0] → [-1,2] → [1,1] ?
In the C++ solution, the visited coordinates are stored in a map, using hashes as keys. In the Java solution, the “hashCode” method is never used.
Spent 40 mins debugging… found out my mistake was
coordinate.row == x && coordinate.row == y.
I know how that feels. Sometimes I try to speed run these questions but that ALWAYS leads to misreading something and spending more time than I should’ve before.
How do we know that this is the minimum number of moves to get to the endpoint?
Because the board is infinite, We should use BFS to traverse level by level and return the shortest/closest/minimum steps that get us to our target coordinate. So, we don’t know where it is but by radiating outwards we are guaranteed to hit it soon or later.
My solution is not that different from the solution presented above. I tried the same test case (2, 112) with my solution but it failed due to “Time Limit Exceeded”.
Although it is clean and easy to read, using a hashset for keeping track of the visited nodes causes TLE while submitting LeetCode 1197.
We can use a bitmap (two dimensional boolean array) instead to keep track of the the visited indices.
A boolean array of size 605x605 makes sure we are covered and not using any negative index.
This is more of a conceptual question that asks what happens if the board is infinite. Leetcode (and competitive programming) is not real interview and a grid of fixed size won’t solve infinite board. See the last section of https://algo.monster/problems/getting_started
While calculating the time complexity, why we consider the square to be of 4x * 4y area? Shouldn’t it be 2x * 2y? It doesn’t affect the time complexity, but I want to understand how 4x * 4y was calculated.
The C# environment on this one didn’t include ‘using System.Collections.Generic;’ like all the previous problems did
Correct me if I’m wrong. I think the square is indeed to be of 4x * 4y area. For example, the target is at somewhere with row ( i.e y ) > 0 and col (i.e x ) > 0 and we want to move from (0, 0) to (target_row, target_col) or ( y, x ). As you can observe in the code snippet, we have "int[] deltaRow = {-2, -2, -1, 1, 2, 2, 1, -1}; ", so the knight can move towards the target_row with one cell or two cells. Then how many steps do we need to go to target_row? It’s target_row/1 or y/1! (We ignore the case that knight can move back which is the case of “-2” and “-1” in the deltaRow because we consider we would have potentially visited most of the cells inside a square.) And the largest side of the square is when we take target_row/1 or y/1 steps with each step moves 2 units. This gives y/1*2 = 2y and by symmetry, in the direction of negative target_row we also have 2y. Thus the total is 4y. Similarly, we have 4x.
Hope this helps :))
Another solution (same logic, but using list comprehension to build the neighbors list):
def get_knight_shortest_path(x: int, y: int) -> int:
if (0, 0) == (x, y):
return 0
def get_neighbors(coord: Tuple[int, int]) -> List[Tuple[int, int]]:
row, col = coord
deltas = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]
return [(row + delta_row, col + delta_col) for delta_row, delta_col in deltas]
steps = 1
queue = deque([(0, 0)])
visited = set([(0, 0)])
while queue:
for _ in range(len(queue)):
coord = queue.popleft()
for neighbor in get_neighbors(coord):
if neighbor in visited:
continue
if neighbor == (x, y):
return steps
visited.add(neighbor)
queue.append(neighbor)
steps += 1
return -1
def get_neighbors(x, y):
offsets = [
(1, 2),
(2, 1),
(2, -1),
(1, -2),
(-1, -2),
(-2, -1),
(-2, 1),
(-1, 2),
]
for x_offset, y_offset in offsets:
yield x + x_offset, y + y_offset
def get_knight_shortest_path(x: int, y: int) -> int:
queue = deque([(0, 0)])
step = 0
visited = set()
while queue:
length = len(queue)
for _ in range(length):
xi, yi = queue.popleft()
visited.add((xi, yi))
if xi == x and yi == y:
return step
for xj, yj in get_neighbors(xi, yi):
if (xj, yj) in visited:
continue
queue.append((xj, yj))
step += 1
// short math solution using java
public static int getKnightShortestPath(int x, int y) {
int grid = {
{4,3,4,3,4,5,4},
{3,4,3,4,3,4,5},
{2,3,2,3,4,3,4},
{3,2,3,2,3,4,3},
{2,1,4,3,2,3,4},
{3,2,1,2,3,4,3},
{0,3,2,3,2,3,4},
};
return Math.max(Math.abs(x/7), Math.abs(y/7)) * 4 + grid[6-Math.abs(x%7)][Math.abs(y%7)];
}