Posibles movimientos de caballo

Dado un tablero de ajedrez de dimensión m*n. Encuentre la cantidad de movimientos posibles en los que se puede mover el caballo en un tablero de ajedrez desde una posición dada. Si mat[i][j] = 1, entonces el bloque se llena con otra cosa, de lo contrario, está vacío. Suponga que el tablero consta de todas las piezas del mismo color, es decir, no hay bloques atacados. 

Ejemplos: 

Input : mat[][] = {{1, 0, 1, 0},
                   {0, 1, 1, 1},
                   {1, 1, 0, 1},
                   {0, 1, 1, 1}}
        pos = (2, 2)
Output : 4
Knight can moved from (2, 2) to (0, 1), (0, 3), 
(1, 0) ans (3, 0).

Podemos observar que el caballo en un tablero de ajedrez se mueve: 

1. Dos movimientos horizontales y un movimiento vertical 
2. Dos movimientos verticales y un movimiento horizontal

La idea es almacenar todos los movimientos posibles del caballo y luego contar el número de movimientos válidos. Un movimiento no será válido si: 

1. Un bloque ya está ocupado por otra pieza. 
2. Mover está fuera del tablero de ajedrez.

Implementación:

// CPP program to find number of possible moves of knight
#include <bits/stdc++.h>
#define n 4
#define m 4
using namespace std;
 
// To calculate possible moves
int findPossibleMoves(int mat[n][m], int p, int q)
{
    // All possible moves of a knight
    int X[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int Y[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
    int count = 0;
 
    // Check if each possible move is valid or not
    for (int i = 0; i < 8; i++) {
 
        // Position of knight after move
        int x = p + X[i];
        int y = q + Y[i];
 
        // count valid moves
        if (x >= 0 && y >= 0 && x < n && y < m
            && mat[x][y] == 0)
            count++;
    }
 
    // Return number of possible moves
    return count;
}
 
// Driver program to check findPossibleMoves()
int main()
{
    int mat[n][m] = { { 1, 0, 1, 0 },
                      { 0, 1, 1, 1 },
                      { 1, 1, 0, 1 },
                      { 0, 1, 1, 1 } };
 
    int p = 2, q = 2;
 
    cout << findPossibleMoves(mat, p, q);
 
    return 0;
}

// Java program to find number of possible moves of knight
public class Main {
public static final int n = 4;
public static final int m = 4;
 
    // To calculate possible moves
    static int findPossibleMoves(int mat[][], int p, int q)
    {
        // All possible moves of a knight
        int X[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
        int Y[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
 
        int count = 0;
 
        // Check if each possible move is valid or not
        for (int i = 0; i < 8; i++) {
 
            // Position of knight after move
            int x = p + X[i];
            int y = q + Y[i];
 
            // count valid moves
            if (x >= 0 && y >= 0 && x < n && y < m
                && mat[x][y] == 0)
                count++;
        }
 
        // Return number of possible moves
        return count;
    }
 
    // Driver program to check findPossibleMoves()
    public static void main(String[] args)
    {
        int mat[][] = { { 1, 0, 1, 0 },
                        { 0, 1, 1, 1 },
                        { 1, 1, 0, 1 },
                        { 0, 1, 1, 1 } };
 
        int p = 2, q = 2;
 
        System.out.println(findPossibleMoves(mat, p, q));
    }
}

# Python3 program to find number
# of possible moves of knight
n = 4;
m = 4;
 
# To calculate possible moves
def findPossibleMoves(mat, p, q):
    global n, m;
     
    # All possible moves of a knight
    X = [2, 1, -1, -2, -2, -1, 1, 2];
    Y = [1, 2, 2, 1, -1, -2, -2, -1];
 
    count = 0;
 
    # Check if each possible move
    # is valid or not
    for i in range(8):
         
        # Position of knight after move
        x = p + X[i];
        y = q + Y[i];
 
        # count valid moves
        if(x >= 0 and y >= 0 and x < n and
           y < m and mat[x][y] == 0):
            count += 1;
 
    # Return number of possible moves
    return count;
 
# Driver code
if __name__ == '__main__':
    mat = [[1, 0, 1, 0], [0, 1, 1, 1],
           [1, 1, 0, 1], [0, 1, 1, 1]];
 
    p, q = 2, 2;
 
    print(findPossibleMoves(mat, p, q));
 
# This code is contributed by 29AjayKumar

// C# program to find number of
// possible moves of knight
using System;
 
class GFG
{
    static int n = 4;
    static int m = 4;
 
    // To calculate
    // possible moves
    static int findPossibleMoves(int [,]mat,
                                 int p, int q)
    {
        // All possible moves
        // of a knight
        int []X = { 2, 1, -1, -2,
                   -2, -1, 1, 2 };
        int []Y = { 1, 2, 2, 1,
                   -1, -2, -2, -1 };
 
        int count = 0;
 
        // Check if each possible
        // move is valid or not
        for (int i = 0; i < 8; i++)
        {
 
            // Position of knight
            // after move
            int x = p + X[i];
            int y = q + Y[i];
 
            // count valid moves
            if (x >= 0 && y >= 0 &&
                x < n && y < m &&
                mat[x, y] == 0)
                count++;
        }
 
        // Return number
        // of possible moves
        return count;
    }
 
    // Driver Code
    static public void Main ()
    {
        int [,]mat = { { 1, 0, 1, 0 },
                       { 0, 1, 1, 1 },
                       { 1, 1, 0, 1 },
                       { 0, 1, 1, 1 }};
 
        int p = 2, q = 2;
 
        Console.WriteLine(findPossibleMoves(mat,
                                            p, q));
    }
}
 
// This code is contributed by m_kit

<?php
// PHP program to find number
// of possible moves of knight
$n = 4;
$m = 4;
 
// To calculate possible moves
function findPossibleMoves($mat,
                           $p, $q)
{
    global $n;
    global $m;
     
    // All possible moves
    // of a knight
    $X = array(2, 1, -1, -2,
              -2, -1, 1, 2);
    $Y = array(1, 2, 2, 1,
              -1, -2, -2, -1);
 
    $count = 0;
 
    // Check if each possible
    // move is valid or not
    for ($i = 0; $i < 8; $i++)
    {
 
        // Position of
        // knight after move
        $x = $p + $X[$i];
        $y = $q + $Y[$i];
 
        // count valid moves
        if ($x >= 0 && $y >= 0 &&
            $x < $n && $y < $m &&
            $mat[$x][$y] == 0)
            $count++;
    }
 
    // Return number
    // of possible moves
    return $count;
}
 
// Driver Code
$mat = array(array(1, 0, 1, 0),
             array(0, 1, 1, 1),
             array(1, 1, 0, 1),
             array(0, 1, 1, 1));
 
$p = 2; $q = 2;
 
echo findPossibleMoves($mat,
                       $p, $q);
 
// This code is contributed by ajit
?>

<script>
    // Javascript program to find number of possible moves of knight
     
    let n = 4;
    let m = 4;
     
    // To calculate possible moves
    function findPossibleMoves(mat, p, q)
    {
        // All possible moves of a knight
        let X = [ 2, 1, -1, -2, -2, -1, 1, 2 ];
        let Y = [ 1, 2, 2, 1, -1, -2, -2, -1 ];
   
        let count = 0;
   
        // Check if each possible move is valid or not
        for (let i = 0; i < 8; i++) {
   
            // Position of knight after move
            let x = p + X[i];
            let y = q + Y[i];
   
            // count valid moves
            if (x >= 0 && y >= 0 && x < n && y < m && mat[x][y] == 0)
                count++;
        }
   
        // Return number of possible moves
        return count;
    }
     
    let mat = [ [ 1, 0, 1, 0 ],
               [ 0, 1, 1, 1 ],
               [ 1, 1, 0, 1 ],
               [ 0, 1, 1, 1 ] ];
   
    let p = 2, q = 2;
 
    document.write(findPossibleMoves(mat, p, q));
     
</script>

4

Tiempo Complejidad: O(1) 
Espacio Auxiliar: O(1)

Este artículo es una contribución de Aarti_Rathi y nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.