Minimum knight moves

Breadth-First Search

41.8% acceptance

Mar 31, 2026

1564

411

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_knight_moves(x: i32, y: i32) -> i32 {
    // BFS from (0,0) to (|x|, |y|) using symmetry
    use std::collections::VecDeque;
    let x = x.abs();
    let y = y.abs();
    if x == 0 && y == 0 {
      return 0;
    }
    let offset = 2;
    let size = 310 + offset;
    let mut visited = vec![vec![false; size as usize]; size as usize];
    let mut queue = VecDeque::new();
    queue.push_back((offset, offset, 0));
    visited[offset as usize][offset as usize] = true;
    let tx = (x + offset) as usize;
    let ty = (y + offset) as usize;
    let dirs = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)];
    while let Some((cx, cy, steps)) = queue.pop_front() {
      for &(dx, dy) in &dirs {
        let nx = cx + dx;
        let ny = cy + dy;
        if nx >= 0 && ny >= 0 && (nx as usize) < size as usize && (ny as usize) < size as usize && !visited[nx as usize][ny as usize] {
          if nx as usize == tx && ny as usize == ty {
            return steps + 1;
          }
          visited[nx as usize][ny as usize] = true;
          queue.push_back((nx, ny, steps + 1));
        }
      }
    }
    -1
  }
}