Número de bloques en un tablero de ajedrez a los que puede moverse un caballo en exactamente k movimientos

Dados los números enteros i, j, k y n donde (i, j) es la posición inicial del caballo en un tablero de ajedrez de n * n , la tarea es encontrar el número de posiciones a las que puede moverse el caballo en exactamente k movimientos.
Ejemplos: 
 

Entrada: i = 5, j = 5, k = 1, n = 10 
Salida: 8
Entrada: i = 0, j = 0, k = 2, n = 10 
Salida: 10 
El caballo puede ver un total de 10 posiciones diferentes en 2. Muevete. 
 

Enfoque: Use un enfoque recursivo para resolver el problema. 
Primero encuentre todas las posiciones posibles a las que se puede mover el caballo, de modo que si la posición inicial es i, j . Llegue a todas las ubicaciones válidas en un solo movimiento y encuentre recursivamente todas las posiciones posibles a las que el caballo pueda moverse en k – 1 pasos desde allí. El caso base de esta recursión es cuando k == 0 (no se puede realizar ningún movimiento), entonces marcaremos la posición del tablero de ajedrez como visitada si no está marcada y aumentaremos la cuenta. Finalmente, muestre el conteo.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// function that will be called recursively
int recursive_solve(int i, int j, int steps, int n,
                      map<pair<int, int>, int> &m)
{
    // If there's no more move to make and
    // this position hasn't been visited before
    if (steps == 0 && m[make_pair(i, j)] == 0) {
 
        // mark the position
        m[make_pair(i, j)] = 1;
 
        // increase the count       
        return 1;
    }
     
    int res = 0;
    if (steps > 0) {
 
        // valid movements for the knight
        int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
        int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
 
        // find all the possible positions
        // where knight can move from i, j
        for (int k = 0; k < 8; k++) {
 
            // if the positions lies within the
            // chessboard
            if ((dx[k] + i) >= 0
                && (dx[k] + i) <= n - 1
                && (dy[k] + j) >= 0
                && (dy[k] + j) <= n - 1) {
 
                // call the function with k-1 moves left
                res += recursive_solve(dx[k] + i, dy[k] + j,
                                       steps - 1, n, m);
            }
        }
    }
    return res;
}
 
// find all the positions where the knight can
// move after k steps
int solve(int i, int j, int steps, int n)
{
    map<pair<int, int>, int> m;
    return recursive_solve(i, j, steps, n, m);
}
 
// driver code
int main()
{
    int i = 0, j = 0, k = 2, n = 10;
 
    cout << solve(i, j, k, n);
 
    return 0;
}

// Java implementation of above approach
import java.util.*;
import java.awt.Point;
public class GFG
{
 
  // function that will be called recursively
  static int recursive_solve(int i, int j, int steps, int n,
                             HashMap<Point,Integer> m)
  {
 
    // If there's no more move to make and
    // this position hasn't been visited before
    if (steps == 0 && !m.containsKey(new Point(i, j)))
    {
 
      // mark the position
      m.put(new Point(i, j), 1);
 
      // increase the count       
      return 1;
    }
    int res = 0;
    if (steps > 0)
    {
 
      // valid movements for the knight
      int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
      int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
 
      // find all the possible positions
      // where knight can move from i, j
      for (int k = 0; k < 8; k++)
      {
 
        // if the positions lies within the
        // chessboard
        if ((dx[k] + i) >= 0
            && (dx[k] + i) <= n - 1
            && (dy[k] + j) >= 0
            && (dy[k] + j) <= n - 1)
        {
 
          // call the function with k-1 moves left
          res += recursive_solve(dx[k] + i, dy[k] + j,
                                 steps - 1, n, m);
        }
      }
    }
    return res;
  }
 
  // find all the positions where the knight can
  // move after k steps
  static int solve(int i, int j, int steps, int n)
  {
    HashMap<Point, Integer> m = new HashMap<>();
    return recursive_solve(i, j, steps, n, m);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int i = 0, j = 0, k = 2, n = 10;
    System.out.print(solve(i, j, k, n));
  }
}
 
 
// This code is contributed by divyeshrabadiya07.

# Python3 implementation of above approach
from collections import defaultdict
 
# Function that will be called recursively
def recursive_solve(i, j, steps, n, m):
 
    # If there's no more move to make and
    # this position hasn't been visited before
    if steps == 0 and m[(i, j)] == 0:
 
        # mark the position
        m[(i, j)] = 1
 
        # increase the count        
        return 1
     
    res = 0
    if steps > 0:
 
        # valid movements for the knight
        dx = [-2, -1, 1, 2, -2, -1, 1, 2]
        dy = [-1, -2, -2, -1, 1, 2, 2, 1]
 
        # find all the possible positions
        # where knight can move from i, j
        for k in range(0, 8):
 
            # If the positions lies
            # within the chessboard
            if (dx[k] + i >= 0 and
                dx[k] + i <= n - 1 and
                dy[k] + j >= 0 and
                dy[k] + j <= n - 1):
 
                # call the function with k-1 moves left
                res += recursive_solve(dx[k] + i, dy[k] + j,
                                       steps - 1, n, m)
     
    return res
 
# Find all the positions where the
# knight can move after k steps
def solve(i, j, steps, n):
 
    m = defaultdict(lambda:0)
    return recursive_solve(i, j, steps, n, m)
 
# Driver code
if __name__ == "__main__":
 
    i, j, k, n = 0, 0, 2, 10
     
    print(solve(i, j, k, n))
 
# This code is contributed by Rituraj Jain

// C# implementation of above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
// function that will be called recursively
static int recursive_solve(int i, int j, int steps, int n,
                      Dictionary<Tuple<int,int>,int>m)
{
    // If there's no more move to make and
    // this position hasn't been visited before
    if (steps == 0 && !m.ContainsKey(new Tuple<int,int>(i, j))) {
 
        // mark the position
        m[new Tuple<int,int>(i, j)] = 1;
 
        // increase the count       
        return 1;
    }
     
    int res = 0;
 
    if (steps > 0) {
 
        // valid movements for the knight
        int []dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
        int []dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
 
        // find all the possible positions
        // where knight can move from i, j
        for (int k = 0; k < 8; k++) {
 
            // if the positions lies within the
            // chessboard
            if ((dx[k] + i) >= 0
                && (dx[k] + i) <= n - 1
                && (dy[k] + j) >= 0
                && (dy[k] + j) <= n - 1) {
 
                // call the function with k-1 moves left
                res += recursive_solve(dx[k] + i, dy[k] + j,
                                       steps - 1, n, m);
            }
        }
    }
    return res;
}
 
// find all the positions where the knight can
// move after k steps
static int solve(int i, int j, int steps, int n)
{
    Dictionary<Tuple<int,int>,int> m=new Dictionary<Tuple<int,int>,int>();
    return recursive_solve(i, j, steps, n, m);
}
 
// driver code
public static void Main(params string []args)
{
    int i = 0, j = 0, k = 2, n = 10;
 
    Console.Write(solve(i, j, k, n));
 
}
}

<script>
    // Javascript implementation of above approach
     
    // function that will be called recursively
    function recursive_solve(i, j, steps, n, m)
    {
        // If there's no more move to make and
        // this position hasn't been visited before
        if (steps == 0 && !m.has([i, j])) {
 
            // mark the position
            m[[i, j]] = 1;
 
            // increase the count      
            return 1;
        }
 
        let res = 0;
 
        if (steps > 0) {
 
            // valid movements for the knight
            let dx = [ -2, -1, 1, 2, -2, -1, 1, 2 ];
            let dy = [ -1, -2, -2, -1, 1, 2, 2, 1 ];
 
            // find all the possible positions
            // where knight can move from i, j
            for (let k = 0; k < 8; k++) {
 
                // if the positions lies within the
                // chessboard
                if ((dx[k] + i) >= 0
                    && (dx[k] + i) <= n - 1
                    && (dy[k] + j) >= 0
                    && (dy[k] + j) <= n - 1) {
 
                    // call the function with k-1 moves left
                    res += recursive_solve(dx[k] + i, dy[k] + j,
                                           steps - 1, n, m);
                }
            }
        }
        return res;
    }
 
    // find all the positions where the knight can
    // move after k steps
    function solve(i, j, steps, n)
    {
        let m = new Map();
        return recursive_solve(i, j, steps, n, m)-2;
    }
     
    let i = 0, j = 0, k = 2, n = 10;
  
    document.write(solve(i, j, k, n));
 
// This code is contributed by rameshtravel07.
</script>

10