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

Rust Solution

struct Solution;

#[derive(PartialEq, Eq, Hash, Debug, Copy, Clone)]
struct Point {
    x: i32,
    y: i32,
}

impl Point {
    fn new(x: i32, y: i32) -> Self {
        Point { x, y }
    }
}

#[derive(PartialEq, Eq, Copy, Clone)]
struct Knight {
    point: Point,
    step: i32,
}

impl Knight {
    fn new(point: Point, step: i32) -> Self {
        Knight { point, step }
    }
    fn next(&self) -> Vec<Knight> {
        let offsets: [[i32; 2]; 8] = [
            [2, 1],
            [1, 2],
            [-1, 2],
            [-2, 1],
            [-2, -1],
            [-1, -2],
            [1, -2],
            [2, -1],
        ];
        let mut res: Vec<Knight> = vec![];
        let x = self.point.x;
        let y = self.point.y;
        let step = self.step;
        for offset in offsets.iter() {
            let knight = Knight::new(Point::new(x + offset[0], y + offset[1]), step + 1);
            res.push(knight);
        }
        res
    }
}

use std::collections::HashSet;
use std::collections::VecDeque;

impl Solution {
    fn min_knight_moves(x: i32, y: i32) -> i32 {
        let end = Point::new(i32::min(x.abs(), y.abs()), i32::max(x.abs(), y.abs()));
        let mut hs: HashSet<Point> = HashSet::new();
        let mut queue: VecDeque<Knight> = VecDeque::new();
        hs.insert(Point::new(0, 0));
        queue.push_back(Knight::new(Point::new(0, 0), 0));
        while let Some(knight) = queue.pop_front() {
            if knight.point == end {
                return knight.step;
            } else {
                let next = knight.next();
                for knight in next {
                    if knight.point.y > 0 && knight.point.x <= knight.point.y {
                        if hs.insert(knight.point) {
                            queue.push_back(knight);
                        }
                    }
                }
            }
        }
        -1
    }
}

#[test]
fn test() {
    let x = 2;
    let y = 1;
    assert_eq!(Solution::min_knight_moves(x, y), 1);
    let x = 5;
    let y = 5;
    assert_eq!(Solution::min_knight_moves(x, y), 4);
}

struct Solution;

use std::mem::swap;

impl Solution {
    fn min_knight_moves(mut x: i32, mut y: i32) -> i32 {
        x = x.abs();
        y = y.abs();
        if x < y {
            swap(&mut x, &mut y);
        }
        if x == 1 && y == 0 {
            return 3;
        }
        if x == 2 && y == 2 {
            return 4;
        }
        let delta = x - y;
        if y > delta {
            delta - 2 * ((delta - y) as f64 / 3.0).floor() as i32
        } else {
            delta - 2 * ((delta - y) as f64 / 4.0).floor() as i32
        }
    }
}

#[test]
fn test() {
    let x = 2;
    let y = 1;
    assert_eq!(Solution::min_knight_moves(x, y), 1);
    let x = 5;
    let y = 5;
    assert_eq!(Solution::min_knight_moves(x, y), 4);
}

Having problems with this solution? Click here to submit an issue on github.