Steps by Knight | Practice Medium 0 attempts
GeeksforGeeks ↗

Steps by Knight | Practice

Medium GraphBFSDFS GeeksforGeeks

A knight sits on one square of an N×N chessboard and must reach another square, moving only in standard L-shaped knight moves. Find the fewest moves needed to get from the source square to the target square.

Input Format
Implement minSteps(n, src, dest). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
n = 6
src = [3,4]
dest = [0,0]
Output
3

Example 2

Input
n = 1
src = [0,0]
dest = [0,0]
Output
0

Example 3

Input
n = 2
src = [0,0]
dest = [1,1]
Output
-1
Constraints
  • 1 <= N <= 1000
Test Cases (3)
Case 1
Args: [6,[3,4],[0,0]] Expected: 3
Case 2
Args: [1,[0,0],[0,0]] Expected: 0
Case 3
Args: [2,[0,0],[1,1]] Expected: -1
Topics
GraphBFSDFS

BFS

javascript
function minSteps(n, src, dest) {
  const moves = [[-2,-1],[-2,1],[-1,-2],[-1,2],[1,-2],[1,2],[2,-1],[2,1]];
  const visited = Array.from({length:n}, ()=>Array(n).fill(false));
  const q = [[src[0],src[1],0]]; visited[src[0]][src[1]] = true;
  let head = 0;
  while (head < q.length) {
    const [r,c,d] = q[head++];
    if (r===dest[0] && c===dest[1]) return d;
    for (const [dr,dc] of moves) {
      const nr=r+dr, nc=c+dc;
      if (nr>=0&&nr<n&&nc>=0&&nc<n&&!visited[nr][nc]) { visited[nr][nc]=true; q.push([nr,nc,d+1]); }
    }
  }
  return -1;
}

Time: O(n²) | Space: O(n²)

Saved in this browser only. Private to you.

JavaScript