Dado un tablero de ajedrez cuadrado de tamaño N x N, se da la posición del caballo y la posición de un objetivo, la tarea es averiguar los pasos mínimos que dará un caballo para alcanzar la posición objetivo.
Ejemplos:
Input : (2, 4) - knight's position, (6, 4) - target cell Output : 2 Input : (4, 5) (1, 1) Output : 3
Ya se discutió un enfoque BFS para resolver el problema anterior en la publicación anterior . En esta publicación, se analiza una solución de programación dinámica.
Explicación del enfoque:
- Caso 1: Si el objetivo no está a lo largo de una fila o una columna de la posición del caballo.
Hagamos un tablero de ajedrez de 8 x 8 celdas. Ahora, digamos que el caballo está en (3, 3) y el objetivo está en (7, 8). Hay 8 movimientos posibles desde la posición actual del caballo, es decir (2, 1), (1, 2), (4, 1), (1, 4), (5, 2), (2, 5), (5 , 4), (4, 5). Pero, entre estos solo dos movimientos (5, 4) y (4, 5) serán hacia el objetivo y todos los demás se alejarán del objetivo. Entonces, para encontrar los pasos mínimos, vaya a (4, 5) o (5, 4). Ahora, calcule los pasos mínimos tomados de (4, 5) y (5, 4) para alcanzar el objetivo. Esto se calcula mediante programación dinámica. Por lo tanto, esto da como resultado los pasos mínimos de (3, 3) a (7, 8). - Caso 2: Si el objetivo está a lo largo de una fila o una columna de la posición del caballo.
Hagamos un tablero de ajedrez de 8 x 8 celdas. Ahora, digamos que el caballo está en (4, 3) y el objetivo está en (4, 7). Hay 8 movimientos posibles, pero hacia el objetivo, solo hay 4 movimientos, es decir (5, 5), (3, 5), (2, 4), (6, 4). Como, (5, 5) es equivalente a (3, 5) y (2, 4) es equivalente a (6, 4). Entonces, de estos 4 puntos, se puede convertir en 2 puntos. Tomando (5, 5) y (6, 4) (aquí). Ahora, calcule los pasos mínimos tomados desde estos dos puntos para alcanzar el objetivo. Esto se calcula mediante programación dinámica. Por lo tanto, esto da como resultado los pasos mínimos de (4, 3) a (4, 7).
Excepción: cuando el caballo estará en la esquina y el objetivo es tal que la diferencia de las coordenadas x e y con la posición del caballo es (1, 1) o viceversa. Entonces los pasos mínimos serán 4.
Ecuación de programación dinámica:
1) dp[diffOfX][diffOfY] son los pasos mínimos tomados desde la posición del caballo hasta la posición del objetivo.
2) dp[diffOfX][diffOfY] = dp[diffOfY][diffOfX] .
donde, diffOfX = diferencia entre la coordenada x del caballero y la coordenada x del objetivo
diffOfY = diferencia entre la coordenada y del caballero y la coordenada y del objetivo
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for minimum steps for
// a knight to reach target position
#include <bits/stdc++.h>
using namespace std;
// initializing the matrix.
int dp[8][8] = { 0 };
int getsteps(int x, int y,
int tx, int ty)
{
// if knight is on the target
// position return 0.
if (x == tx && y == ty)
return dp[0][0];
else {
// if already calculated then return
// that value. Taking absolute difference.
if (dp[abs(x - tx)][abs(y - ty)] != 0)
return dp[abs(x - tx)][abs(y - ty)];
else {
// there will be two distinct positions
// from the knight towards a target.
// if the target is in same row or column
// as of knight than there can be four
// positions towards the target but in that
// two would be the same and the other two
// would be the same.
int x1, y1, x2, y2;
// (x1, y1) and (x2, y2) are two positions.
// these can be different according to situation.
// From position of knight, the chess board can be
// divided into four blocks i.e.. N-E, E-S, S-W, W-N .
if (x <= tx) {
if (y <= ty) {
x1 = x + 2;
y1 = y + 1;
x2 = x + 1;
y2 = y + 2;
} else {
x1 = x + 2;
y1 = y - 1;
x2 = x + 1;
y2 = y - 2;
}
} else {
if (y <= ty) {
x1 = x - 2;
y1 = y + 1;
x2 = x - 1;
y2 = y + 2;
} else {
x1 = x - 2;
y1 = y - 1;
x2 = x - 1;
y2 = y - 2;
}
}
// ans will be, 1 + minimum of steps
// required from (x1, y1) and (x2, y2).
dp[abs(x - tx)][abs(y - ty)] =
min(getsteps(x1, y1, tx, ty),
getsteps(x2, y2, tx, ty)) + 1;
// exchanging the coordinates x with y of both
// knight and target will result in same ans.
dp[abs(y - ty)][abs(x - tx)] =
dp[abs(x - tx)][abs(y - ty)];
return dp[abs(x - tx)][abs(y - ty)];
}
}
}
// Driver Code
int main()
{
int i, n, x, y, tx, ty, ans;
// size of chess board n*n
n = 100;
// (x, y) coordinate of the knight.
// (tx, ty) coordinate of the target position.
x = 4;
y = 5;
tx = 1;
ty = 1;
// (Exception) these are the four corner points
// for which the minimum steps is 4.
if ((x == 1 && y == 1 && tx == 2 && ty == 2) ||
(x == 2 && y == 2 && tx == 1 && ty == 1))
ans = 4;
else if ((x == 1 && y == n && tx == 2 && ty == n - 1) ||
(x == 2 && y == n - 1 && tx == 1 && ty == n))
ans = 4;
else if ((x == n && y == 1 && tx == n - 1 && ty == 2) ||
(x == n - 1 && y == 2 && tx == n && ty == 1))
ans = 4;
else if ((x == n && y == n && tx == n - 1 && ty == n - 1) ||
(x == n - 1 && y == n - 1 && tx == n && ty == n))
ans = 4;
else {
// dp[a][b], here a, b is the difference of
// x & tx and y & ty respectively.
dp[1][0] = 3;
dp[0][1] = 3;
dp[1][1] = 2;
dp[2][0] = 2;
dp[0][2] = 2;
dp[2][1] = 1;
dp[1][2] = 1;
ans = getsteps(x, y, tx, ty);
}
cout << ans << endl;
return 0;
}
Java
//Java code for minimum steps for
// a knight to reach target position
public class GFG {
// initializing the matrix.
static int dp[][] = new int[8][8];
static int getsteps(int x, int y,
int tx, int ty) {
// if knight is on the target
// position return 0.
if (x == tx && y == ty) {
return dp[0][0];
} else // if already calculated then return
// that value. Taking absolute difference.
if (dp[ Math.abs(x - tx)][ Math.abs(y - ty)] != 0) {
return dp[ Math.abs(x - tx)][ Math.abs(y - ty)];
} else {
// there will be two distinct positions
// from the knight towards a target.
// if the target is in same row or column
// as of knight than there can be four
// positions towards the target but in that
// two would be the same and the other two
// would be the same.
int x1, y1, x2, y2;
// (x1, y1) and (x2, y2) are two positions.
// these can be different according to situation.
// From position of knight, the chess board can be
// divided into four blocks i.e.. N-E, E-S, S-W, W-N .
if (x <= tx) {
if (y <= ty) {
x1 = x + 2;
y1 = y + 1;
x2 = x + 1;
y2 = y + 2;
} else {
x1 = x + 2;
y1 = y - 1;
x2 = x + 1;
y2 = y - 2;
}
} else if (y <= ty) {
x1 = x - 2;
y1 = y + 1;
x2 = x - 1;
y2 = y + 2;
} else {
x1 = x - 2;
y1 = y - 1;
x2 = x - 1;
y2 = y - 2;
}
// ans will be, 1 + minimum of steps
// required from (x1, y1) and (x2, y2).
dp[ Math.abs(x - tx)][ Math.abs(y - ty)]
= Math.min(getsteps(x1, y1, tx, ty),
getsteps(x2, y2, tx, ty)) + 1;
// exchanging the coordinates x with y of both
// knight and target will result in same ans.
dp[ Math.abs(y - ty)][ Math.abs(x - tx)]
= dp[ Math.abs(x - tx)][ Math.abs(y - ty)];
return dp[ Math.abs(x - tx)][ Math.abs(y - ty)];
}
}
// Driver Code
static public void main(String[] args) {
int i, n, x, y, tx, ty, ans;
// size of chess board n*n
n = 100;
// (x, y) coordinate of the knight.
// (tx, ty) coordinate of the target position.
x = 4;
y = 5;
tx = 1;
ty = 1;
// (Exception) these are the four corner points
// for which the minimum steps is 4.
if ((x == 1 && y == 1 && tx == 2 && ty == 2)
|| (x == 2 && y == 2 && tx == 1 && ty == 1)) {
ans = 4;
} else if ((x == 1 && y == n && tx == 2 && ty == n - 1)
|| (x == 2 && y == n - 1 && tx == 1 && ty == n)) {
ans = 4;
} else if ((x == n && y == 1 && tx == n - 1 && ty == 2)
|| (x == n - 1 && y == 2 && tx == n && ty == 1)) {
ans = 4;
} else if ((x == n && y == n && tx == n - 1 && ty == n - 1)
|| (x == n - 1 && y == n - 1 && tx == n && ty == n)) {
ans = 4;
} else {
// dp[a][b], here a, b is the difference of
// x & tx and y & ty respectively.
dp[1][0] = 3;
dp[0][1] = 3;
dp[1][1] = 2;
dp[2][0] = 2;
dp[0][2] = 2;
dp[2][1] = 1;
dp[1][2] = 1;
ans = getsteps(x, y, tx, ty);
}
System.out.println(ans);
}
}
/*This code is contributed by PrinciRaj1992*/
Python3
# Python3 code for minimum steps for # a knight to reach target position # initializing the matrix. dp = [[0 for i in range(8)] for j in range(8)]; def getsteps(x, y, tx, ty): # if knight is on the target # position return 0. if (x == tx and y == ty): return dp[0][0]; # if already calculated then return # that value. Taking absolute difference. elif(dp[abs(x - tx)][abs(y - ty)] != 0): return dp[abs(x - tx)][abs(y - ty)]; else: # there will be two distinct positions # from the knight towards a target. # if the target is in same row or column # as of knight than there can be four # positions towards the target but in that # two would be the same and the other two # would be the same. x1, y1, x2, y2 = 0, 0, 0, 0; # (x1, y1) and (x2, y2) are two positions. # these can be different according to situation. # From position of knight, the chess board can be # divided into four blocks i.e.. N-E, E-S, S-W, W-N . if (x <= tx): if (y <= ty): x1 = x + 2; y1 = y + 1; x2 = x + 1; y2 = y + 2; else: x1 = x + 2; y1 = y - 1; x2 = x + 1; y2 = y - 2; elif (y <= ty): x1 = x - 2; y1 = y + 1; x2 = x - 1; y2 = y + 2; else: x1 = x - 2; y1 = y - 1; x2 = x - 1; y2 = y - 2; # ans will be, 1 + minimum of steps # required from (x1, y1) and (x2, y2). dp[abs(x - tx)][abs(y - ty)] = \ min(getsteps(x1, y1, tx, ty), getsteps(x2, y2, tx, ty)) + 1; # exchanging the coordinates x with y of both # knight and target will result in same ans. dp[abs(y - ty)][abs(x - tx)] = \ dp[abs(x - tx)][abs(y - ty)]; return dp[abs(x - tx)][abs(y - ty)]; # Driver Code if __name__ == '__main__': # size of chess board n*n n = 100; # (x, y) coordinate of the knight. # (tx, ty) coordinate of the target position. x = 4; y = 5; tx = 1; ty = 1; # (Exception) these are the four corner points # for which the minimum steps is 4. if ((x == 1 and y == 1 and tx == 2 and ty == 2) or (x == 2 and y == 2 and tx == 1 and ty == 1)): ans = 4; elif ((x == 1 and y == n and tx == 2 and ty == n - 1) or (x == 2 and y == n - 1 and tx == 1 and ty == n)): ans = 4; elif ((x == n and y == 1 and tx == n - 1 and ty == 2) or (x == n - 1 and y == 2 and tx == n and ty == 1)): ans = 4; elif ((x == n and y == n and tx == n - 1 and ty == n - 1) or (x == n - 1 and y == n - 1 and tx == n and ty == n)): ans = 4; else: # dp[a][b], here a, b is the difference of # x & tx and y & ty respectively. dp[1][0] = 3; dp[0][1] = 3; dp[1][1] = 2; dp[2][0] = 2; dp[0][2] = 2; dp[2][1] = 1; dp[1][2] = 1; ans = getsteps(x, y, tx, ty); print(ans); # This code is contributed by PrinciRaj1992
C#
// C# code for minimum steps for
// a knight to reach target position
using System;
public class GFG{
// initializing the matrix.
static int [ , ]dp = new int[8 , 8];
static int getsteps(int x, int y,
int tx, int ty) {
// if knight is on the target
// position return 0.
if (x == tx && y == ty) {
return dp[0 , 0];
} else // if already calculated then return
// that value. Taking Absolute difference.
if (dp[ Math. Abs(x - tx) , Math. Abs(y - ty)] != 0) {
return dp[ Math. Abs(x - tx) , Math. Abs(y - ty)];
} else {
// there will be two distinct positions
// from the knight towards a target.
// if the target is in same row or column
// as of knight than there can be four
// positions towards the target but in that
// two would be the same and the other two
// would be the same.
int x1, y1, x2, y2;
// (x1, y1) and (x2, y2) are two positions.
// these can be different according to situation.
// From position of knight, the chess board can be
// divided into four blocks i.e.. N-E, E-S, S-W, W-N .
if (x <= tx) {
if (y <= ty) {
x1 = x + 2;
y1 = y + 1;
x2 = x + 1;
y2 = y + 2;
} else {
x1 = x + 2;
y1 = y - 1;
x2 = x + 1;
y2 = y - 2;
}
} else if (y <= ty) {
x1 = x - 2;
y1 = y + 1;
x2 = x - 1;
y2 = y + 2;
} else {
x1 = x - 2;
y1 = y - 1;
x2 = x - 1;
y2 = y - 2;
}
// ans will be, 1 + minimum of steps
// required from (x1, y1) and (x2, y2).
dp[ Math. Abs(x - tx) , Math. Abs(y - ty)]
= Math.Min(getsteps(x1, y1, tx, ty),
getsteps(x2, y2, tx, ty)) + 1;
// exchanging the coordinates x with y of both
// knight and target will result in same ans.
dp[ Math. Abs(y - ty) , Math. Abs(x - tx)]
= dp[ Math. Abs(x - tx) , Math. Abs(y - ty)];
return dp[ Math. Abs(x - tx) , Math. Abs(y - ty)];
}
}
// Driver Code
static public void Main() {
int i, n, x, y, tx, ty, ans;
// size of chess board n*n
n = 100;
// (x, y) coordinate of the knight.
// (tx, ty) coordinate of the target position.
x = 4;
y = 5;
tx = 1;
ty = 1;
// (Exception) these are the four corner points
// for which the minimum steps is 4.
if ((x == 1 && y == 1 && tx == 2 && ty == 2)
|| (x == 2 && y == 2 && tx == 1 && ty == 1)) {
ans = 4;
} else if ((x == 1 && y == n && tx == 2 && ty == n - 1)
|| (x == 2 && y == n - 1 && tx == 1 && ty == n)) {
ans = 4;
} else if ((x == n && y == 1 && tx == n - 1 && ty == 2)
|| (x == n - 1 && y == 2 && tx == n && ty == 1)) {
ans = 4;
} else if ((x == n && y == n && tx == n - 1 && ty == n - 1)
|| (x == n - 1 && y == n - 1 && tx == n && ty == n)) {
ans = 4;
} else {
// dp[a , b], here a, b is the difference of
// x & tx and y & ty respectively.
dp[1 , 0] = 3;
dp[0 , 1] = 3;
dp[1 , 1] = 2;
dp[2 , 0] = 2;
dp[0 , 2] = 2;
dp[2 , 1] = 1;
dp[1 , 2] = 1;
ans = getsteps(x, y, tx, ty);
}
Console.WriteLine(ans);
}
}
/*This code is contributed by PrinciRaj1992*/
Javascript
<script>
// JavaScript code for minimum steps for
// a knight to reach target position
// initializing the matrix.
let dp = new Array(8)
for(let i=0;i<8;i++){
dp[i] = new Array(8).fill(0)
}
function getsteps(x,y,tx,ty)
{
// if knight is on the target
// position return 0.
if (x == tx && y == ty)
return dp[0][0];
else {
// if already calculated then return
// that value. Taking absolute difference.
if (dp[Math.abs(x - tx)][Math.abs(y - ty)] != 0)
return dp[Math.abs(x - tx)][Math.abs(y - ty)];
else {
// there will be two distinct positions
// from the knight towards a target.
// if the target is in same row or column
// as of knight than there can be four
// positions towards the target but in that
// two would be the same and the other two
// would be the same.
let x1, y1, x2, y2;
// (x1, y1) and (x2, y2) are two positions.
// these can be different according to situation.
// From position of knight, the chess board can be
// divided into four blocks i.e.. N-E, E-S, S-W, W-N .
if (x <= tx) {
if (y <= ty) {
x1 = x + 2;
y1 = y + 1;
x2 = x + 1;
y2 = y + 2;
} else {
x1 = x + 2;
y1 = y - 1;
x2 = x + 1;
y2 = y - 2;
}
} else {
if (y <= ty) {
x1 = x - 2;
y1 = y + 1;
x2 = x - 1;
y2 = y + 2;
} else {
x1 = x - 2;
y1 = y - 1;
x2 = x - 1;
y2 = y - 2;
}
}
// ans will be, 1 + minimum of steps
// required from (x1, y1) and (x2, y2).
dp[Math.abs(x - tx)][Math.abs(y - ty)] =
Math.min(getsteps(x1, y1, tx, ty),
getsteps(x2, y2, tx, ty)) + 1;
// exchanging the coordinates x with y of both
// knight and target will result in same ans.
dp[Math.abs(y - ty)][Math.abs(x - tx)] =
dp[Math.abs(x - tx)][Math.abs(y - ty)];
return dp[Math.abs(x - tx)][Math.abs(y - ty)];
}
}
}
// Driver Code
let i, n, x, y, tx, ty, ans;
// size of chess board n*n
n = 100;
// (x, y) coordinate of the knight.
// (tx, ty) coordinate of the target position.
x = 4;
y = 5;
tx = 1;
ty = 1;
// (Exception) these are the four corner points
// for which the minimum steps is 4.
if ((x == 1 && y == 1 && tx == 2 && ty == 2) ||
(x == 2 && y == 2 && tx == 1 && ty == 1))
ans = 4;
else if ((x == 1 && y == n && tx == 2 && ty == n - 1) ||
(x == 2 && y == n - 1 && tx == 1 && ty == n))
ans = 4;
else if ((x == n && y == 1 && tx == n - 1 && ty == 2) ||
(x == n - 1 && y == 2 && tx == n && ty == 1))
ans = 4;
else if ((x == n && y == n && tx == n - 1 && ty == n - 1) ||
(x == n - 1 && y == n - 1 && tx == n && ty == n))
ans = 4;
else
{
// dp[a][b], here a, b is the difference of
// x & tx and y & ty respectively.
dp[1][0] = 3;
dp[0][1] = 3;
dp[1][1] = 2;
dp[2][0] = 2;
dp[0][2] = 2;
dp[2][1] = 1;
dp[1][2] = 1;
ans = getsteps(x, y, tx, ty);
}
document.write(ans,"</br>");
// This code is contributed by shinjanpatra.
</script>
Producción:
3
Complejidad de Tiempo: O(N * M) donde N es el número total de filas y M es el número total de columnas
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA