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]
This problem can be solved using the BFS shortest path model. The search space for this problem is not large, so we can directly use the naive BFS. The solution below also provides the code for bidirectional BFS for reference.
Bidirectional BFS is a common optimization method for BFS. The main implementation ideas are as follows:
Create two queues, q1 and q2, for "start -> end" and "end -> start" search directions, respectively.
Create two hash maps, m1 and m2, to record the visited nodes and their corresponding expansion times (steps).
During each search, prioritize the queue with fewer elements for search expansion. If a node visited from the other direction is found during the expansion, it means the shortest path has been found.
If one of the queues is empty, it means that the search in the current direction cannot continue, indicating that the start and end points are not connected, and there is no need to continue the search.
usestd::collections::VecDeque;constDIR:[(i32,i32);8]=[(-2,1),(2,1),(-1,2),(1,2),(2,-1),(-2,-1),(1,-2),(-1,-2),];implSolution{#[allow(dead_code)]pubfnmin_knight_moves(x:i32,y:i32)->i32{// The original x, y are from [-300, 300]// Let's shift them to [0, 600]letx:i32=x+300;lety:i32=y+300;letmutret=-1;letmutvis:Vec<Vec<bool>>=vec![vec![false;618];618];// <X, Y, Current Steps>letmutq:VecDeque<(i32,i32,i32)>=VecDeque::new();q.push_back((300,300,0));while!q.is_empty(){let(i,j,s)=q.front().unwrap().clone();q.pop_front();ifi==x&&j==y{ret=s;break;}Self::enqueue(&mutvis,&mutq,i,j,s);}ret}#[allow(dead_code)]fnenqueue(vis:&mutVec<Vec<bool>>,q:&mutVecDeque<(i32,i32,i32)>,i:i32,j:i32,cur_step:i32,){letnext_step=cur_step+1;for(dx,dy)inDIR{letx=i+dx;lety=j+dy;ifSelf::check_bounds(x,y)||vis[xasusize][yasusize]{// This <X, Y> pair is either out of bound, or has been visited before// Just ignore this paircontinue;}// Otherwise, add the pair to the queue// Also remember to update the vis vectorvis[xasusize][yasusize]=true;q.push_back((x,y,next_step));}}#[allow(dead_code)]fncheck_bounds(i:i32,j:i32)->bool{i<0||i>600||j<0||j>600}}
usestd::collections::HashMap;usestd::collections::VecDeque;constDIR:[(i32,i32);8]=[(-2,1),(2,1),(-1,2),(1,2),(2,-1),(-2,-1),(1,-2),(-1,-2),];implSolution{#[allow(dead_code)]pubfnmin_knight_moves(x:i32,y:i32)->i32{ifx==0&&y==0{return0;}// Otherwise, let's shift <X, Y> from [-300, 300] -> [0, 600]letx=x+300;lety=y+300;letmutret=-1;// Initialize the two hash map, used to track if a node has been visitedletmutmap_to:HashMap<i32,i32>=HashMap::new();letmutmap_from:HashMap<i32,i32>=HashMap::new();// Input the original statusmap_to.insert(601*300+300,0);map_from.insert(601*x+y,0);letmutq_to:VecDeque<(i32,i32)>=VecDeque::new();letmutq_from:VecDeque<(i32,i32)>=VecDeque::new();// Initialize the two queueq_to.push_back((300,300));q_from.push_back((x,y));while!q_to.is_empty()&&!q_from.is_empty(){letstep=ifq_to.len()<q_from.len(){Self::extend(&mutmap_to,&mutmap_from,&mutq_to)}else{Self::extend(&mutmap_from,&mutmap_to,&mutq_from)};ifstep!=-1{ret=step;break;}}ret}#[allow(dead_code)]fnextend(map_to:&mutHashMap<i32,i32>,map_from:&mutHashMap<i32,i32>,cur_q:&mutVecDeque<(i32,i32)>,)->i32{letn=cur_q.len();for_in0..n{let(i,j)=cur_q.front().unwrap().clone();cur_q.pop_front();// The cur_step here must existletcur_step=map_to.get(&(601*i+j)).unwrap().clone();for(dx,dy)inDIR{letx=i+dx;lety=j+dy;// Check if this node has been visitedifmap_to.contains_key(&(601*x+y)){// Just ignore this nodecontinue;}// Check if this node has been visited by the other sideifmap_from.contains_key(&(601*x+y)){// We found the nodereturn(cur_step+1+map_from.get(&(601*x+y)).unwrap().clone());}// Otherwise, update map_to and push the new node to queuemap_to.insert(601*x+y,cur_step+1);cur_q.push_back((x,y));}}-1}}