Enunciado

Enlace al problema Descripción del problema

Hay un soldado en el punto A del tablero, que necesita llegar al punto B. El movimiento del soldado es hacia abajo o hacia la derecha. En el tablero hay un caballo en el punto C, y los puntos alcanzables por el caballo se consideran puntos de control. Este problema se conoce como "el caballo bloquea al soldado".

El tablero se representa con coordenadas, donde A está en (0,0) y B está en (n,m), con n y m no mayores a 20. La posición del caballo también debe proporcionarse.

Se pide calcular el número de caminos posibles desde A hasta B, asumiendo que el caballo no se mueve.

Formato de entradda

Una línea con cuatro valores: las coordenadas de B y las del caballo.

Formato de salida

Un valor que representa el número total de caminos.

Ejemplo de entrada/salida

Entrada #1
6 6 3 3
Salida #1
6

Nota

El resultado puede ser muy grande.

------------------------------------------------

Análisis

Este problema requiere calcular el número de caminos posibles para un soldado que se mueve solo hacia abajo o hacia la derecha, evitando ciertos puntos controlados por un caballo.

Por ejemplo, en el caso del ejemplo, algunos puntos son inválidos:

  0 1 2 3 4 5 6---coordenadas horizontales
0 A 0 0 0 0 0 0
1 0 0 N 0 N 0 0
2 0 N 0 0 0 N 0
3 0 0 0 C 0 0 0
4 0 N 0 0 0 N 0
5 0 0 N 0 N 0 0
6 0 0 0 0 0 0 0
|-coordenadas verticales

Podemos definir una matriz dp[i][j], donde dp[i][j] representa el número de caminos desde A hasta el punto (i,j). La fórmula para calcular esto es:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Expliccación: Para llegar a un punto, solo se puede venir desde arriba o desde la izquierda, por lo que la suma de ambos da el número total de caminos.

Para evitar problemas en los bordes, se ajustan las coordenadas sumando 1 a cada una. Además, se inicializa dp[0][1] = 1.

Programa

Implementamso el enfoque de dinámica programada:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int bx, by, cx, cy;
unsigned long long dp[25][25];
bool f[25][25];

const int fx[9] = {0, -2, -1, 1, 2, 2, 1, -1, -2};
const int fy[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1};

int main() {
    scanf("%d%d%d%d", &bx, &by, &cx, &cy);
    bx++; by++; cx++; cy++;
    dp[0][1] = 1;

    for(int i = 0; i < 9; i++)
        f[cx + fx[i]][cy + fy[i]] = true;

    for(int i = 1; i <= bx; i++)
        for(int j = 1; j <= by; j++)
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) * (!f[i][j]);

    printf("%lld\n", dp[bx][by]);
    return 0;
}