LeetCode 1197 Minimum Knight Moves

LeetCode 1197 Minimum Knight Moves

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example 1:

Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]

Example 2:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

Constraints:

• |x| + |y| <= 300

Because x and y are constrained to be in range[-300, 300], we can use BFS to find the minimum steps needed to reach target(x, y). Furthermore, we can only consider the case that x >=0 && y >=0 since the chess board is symmetric. The bfs implementation is pretty straightforward. There are two important points you need to be careful with.

1. Pruning. We can limit the search dimension within 310 * 310. Any moves that lead to a position that is outside this box will not yield an optimal result.

2. Initially, you used a Set of type int[] to track visited positions. This caused TLE because you didn’t overwrite the hashCode and equals methods for int[]. As a result, Set uses the default hashCode and equals method when checking if an element is already in the set. For equals(), The default implementation provided by the JDK is based on memory location — two objects are equal if and only if they are stored in the same memory address. For a comprehensive reading, refer to https://dzone.com/articles/working-with-hashcode-and-equals-in-java

O(x * y) runtime and space

题目大意：

象棋一样，走日字到达目标点的最小次数。

解题思路：

这题是最短路径题，第一时间想到BFS。

解题步骤：

这题是最短路径题，第一时间想到BFS。这是一条典型的单源最短路径问题。用Distance BFS模板

1. 建距离map。
2. BFS访问。

注意事项：

1. 有边界限制

Python代码：

def minKnightMoves(self, x: int, y: int) -> int:
	return self.bfs(0, 0, x, y)

def bfs(self, start_x, start_y, target_x, target_y):
	directions = {(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)}
	queue = deque([(start_x, start_y)])
	visited = {(start_x, start_y)}
	distance = {(start_x, start_y): 0}
	while queue:
		node = queue.popleft()
		if node == (target_x, target_y):
			return distance[node]

		for direction in directions:
			neighbor = (node[0] + direction[0], node[1] + direction[1])
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance[neighbor] = distance[node] + 1

注意事项：

1. 用map记录距离一定要将首节点加入到map中，否则求距离时候会NPE。
2. visited我一开始实现用HashSet但因为没有实现equals导致LTE，改成矩阵即可。

Java代码：

int[] directX = new int[]{1, 1,-1,-1,2,2,-2,-2};
int[] directY = new int[]{2,-2,2,-2,1,-1,1,-1};

public int shortestPath(boolean[][] grid, Point source, Point destination) {
	if(grid == null || grid.length == 0 || grid[0].length == 0)
		return -1;
	
	Queue<Point> q = new LinkedList<>();
	Map<Point, Integer> map = new HashMap<>();
	map.put(source, 0); // remember
	boolean[][] visited = new boolean[grid.length][grid[0].length];
	q.offer(source);
	visited[source.x][source.y] = true; // use hashSet is wrong.
	while(!q.isEmpty()) {
		Point p = q.poll();
		if(p.x == destination.x && p.y == destination.y)
			return map.get(p);
		for(Point neighbor : getNeighbors(p)) {
			if(!isValid(grid, neighbor) || visited[neighbor.x][neighbor.y])
				continue;
			q.offer(neighbor);
			visited[neighbor.x][neighbor.y] = true;
			map.put(neighbor, map.get(p) + 1);
		}
	}
	
	return -1;
}

List<Point> getNeighbors(Point point) {
	List<Point> result = new ArrayList<>();
	for(int i = 0; i < 8; i++) {
		result.add(new Point(point.x + directX[i], point.y + directY[i]));
	}
	return result;
}

boolean isValid(boolean[][] grid, Point point) {
	if(point.x >= 0 && point.x < grid.length && point.y >= 0 && point.y < grid[0].length 
			&& !grid[point.x][point.y])
		return true;
	else return false;
}

算法分析：

时间复杂度为棋盘大小O(n*m)，空间复杂度O(n)。