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
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);
}