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. Necesitamos averiguar los pasos mínimos que dará un Caballero para alcanzar la posición objetivo.
Ejemplos:
In above diagram Knight takes 3 step to reach from (4, 5) to (1, 1) (4, 5) -> (5, 3) -> (3, 2) -> (1, 1) as shown in diagram
Enfoque:
este problema puede verse como el camino más corto en un gráfico no ponderado. Por lo tanto, usamos BFS para resolver este problema. Probamos las 8 posiciones posibles a las que un caballo puede llegar desde su posición. Si la posición alcanzable aún no se ha visitado y está dentro del tablero, empujamos este estado a la cola con una distancia 1 más que su estado principal. Finalmente, devolvemos la distancia de la posición objetivo, cuando sale de la cola.
El siguiente código implementa BFS para buscar en las celdas, donde cada celda contiene su coordenada y la distancia desde el Node inicial. En el peor de los casos, el siguiente código visita todas las celdas del tablero, lo que hace que la complejidad del tiempo en el peor de los casos sea O (N ^ 2)
C++
// C++ program to find minimum steps to reach to
// specific cell in minimum moves by Knight
#include <bits/stdc++.h>
using namespace std;
// structure for storing a cell's data
struct cell {
int x, y;
int dis;
cell() {}
cell(int x, int y, int dis)
: x(x), y(y), dis(dis)
{
}
};
// Utility method returns true if (x, y) lies
// inside Board
bool isInside(int x, int y, int N)
{
if (x >= 1 && x <= N && y >= 1 && y <= N)
return true;
return false;
}
// Method returns minimum step
// to reach target position
int minStepToReachTarget(
int knightPos[], int targetPos[],
int N)
{
// x and y direction, where a knight can move
int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
// queue for storing states of knight in board
queue<cell> q;
// push starting position of knight with 0 distance
q.push(cell(knightPos[0], knightPos[1], 0));
cell t;
int x, y;
bool visit[N + 1][N + 1];
// make all cell unvisited
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
visit[i][j] = false;
// visit starting state
visit[knightPos[0]][knightPos[1]] = true;
// loop until we have one element in queue
while (!q.empty()) {
t = q.front();
q.pop();
// if current cell is equal to target cell,
// return its distance
if (t.x == targetPos[0] && t.y == targetPos[1])
return t.dis;
// loop for all reachable states
for (int i = 0; i < 8; i++) {
x = t.x + dx[i];
y = t.y + dy[i];
// If reachable state is not yet visited and
// inside board, push that state into queue
if (isInside(x, y, N) && !visit[x][y]) {
visit[x][y] = true;
q.push(cell(x, y, t.dis + 1));
}
}
}
}
// Driver code to test above methods
int main()
{
int N = 30;
int knightPos[] = { 1, 1 };
int targetPos[] = { 30, 30 };
cout << minStepToReachTarget(knightPos, targetPos, N);
return 0;
}
Java
import java.util.*;
// Java program to find minimum steps to reach to
// specific cell in minimum moves by Knight
class GFG {
// Class for storing a cell's data
static class cell {
int x, y;
int dis;
public cell(int x, int y, int dis)
{
this.x = x;
this.y = y;
this.dis = dis;
}
}
// Utility method returns true if (x, y) lies
// inside Board
static boolean isInside(int x, int y, int N)
{
if (x >= 1 && x <= N && y >= 1 && y <= N)
return true;
return false;
}
// Method returns minimum step
// to reach target position
static int minStepToReachTarget(
int knightPos[], int targetPos[],
int N)
{
// x and y direction, where a knight can move
int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
// queue for storing states of knight in board
Vector<cell> q = new Vector<>();
// push starting position of knight with 0 distance
q.add(new cell(knightPos[0], knightPos[1], 0));
cell t;
int x, y;
boolean visit[][] = new boolean[N + 1][N + 1]; //default initialized to false
// visit starting state
visit[knightPos[0]][knightPos[1]] = true;
// loop until we have one element in queue
while (!q.isEmpty()) {
t = q.firstElement();
q.remove(0);
// if current cell is equal to target cell,
// return its distance
if (t.x == targetPos[0] && t.y == targetPos[1])
return t.dis;
// loop for all reachable states
for (int i = 0; i < 8; i++) {
x = t.x + dx[i];
y = t.y + dy[i];
// If reachable state is not yet visited and
// inside board, push that state into queue
if (isInside(x, y, N) && !visit[x][y]) {
visit[x][y] = true;
q.add(new cell(x, y, t.dis + 1));
}
}
}
return Integer.MAX_VALUE;
}
// Driver code
public static void main(String[] args)
{
int N = 30;
int knightPos[] = { 1, 1 };
int targetPos[] = { 30, 30 };
System.out.println(
minStepToReachTarget(
knightPos, targetPos, N));
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 code to find minimum steps to reach # to specific cell in minimum moves by Knight class cell: def __init__(self, x = 0, y = 0, dist = 0): self.x = x self.y = y self.dist = dist # checks whether given position is # inside the board def isInside(x, y, N): if (x >= 1 and x <= N and y >= 1 and y <= N): return True return False # Method returns minimum step to reach # target position def minStepToReachTarget(knightpos, targetpos, N): # all possible movements for the knight dx = [2, 2, -2, -2, 1, 1, -1, -1] dy = [1, -1, 1, -1, 2, -2, 2, -2] queue = [] # push starting position of knight # with 0 distance queue.append(cell(knightpos[0], knightpos[1], 0)) # make all cell unvisited visited = [[False for i in range(N + 1)] for j in range(N + 1)] # visit starting state visited[knightpos[0]][knightpos[1]] = True # loop until we have one element in queue while(len(queue) > 0): t = queue[0] queue.pop(0) # if current cell is equal to target # cell, return its distance if(t.x == targetpos[0] and t.y == targetpos[1]): return t.dist # iterate for all reachable states for i in range(8): x = t.x + dx[i] y = t.y + dy[i] if(isInside(x, y, N) and not visited[x][y]): visited[x][y] = True queue.append(cell(x, y, t.dist + 1)) # Driver Code if __name__=='__main__': N = 30 knightpos = [1, 1] targetpos = [30, 30] print(minStepToReachTarget(knightpos, targetpos, N)) # This code is contributed by # Kaustav kumar Chanda
C#
// C# program to find minimum steps to reach to
// specific cell in minimum moves by Knight
using System;
using System.Collections.Generic;
class GFG {
// Class for storing a cell's data
public class cell {
public int x, y;
public int dis;
public cell(int x, int y, int dis)
{
this.x = x;
this.y = y;
this.dis = dis;
}
}
// Utility method returns true
// if (x, y) lies inside Board
static bool isInside(int x, int y, int N)
{
if (x >= 1 && x <= N && y >= 1 && y <= N)
return true;
return false;
}
// Method returns minimum step
// to reach target position
static int minStepToReachTarget(int[] knightPos,
int[] targetPos, int N)
{
// x and y direction, where a knight can move
int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };
// queue for storing states of knight in board
Queue<cell> q = new Queue<cell>();
// push starting position of knight with 0 distance
q.Enqueue(new cell(knightPos[0],
knightPos[1], 0));
cell t;
int x, y;
bool[, ] visit = new bool[N + 1, N + 1];
// make all cell unvisited
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
visit[i, j] = false;
// visit starting state
visit[knightPos[0], knightPos[1]] = true;
// loop until we have one element in queue
while (q.Count != 0) {
t = q.Peek();
q.Dequeue();
// if current cell is equal to target cell,
// return its distance
if (t.x == targetPos[0] && t.y == targetPos[1])
return t.dis;
// loop for all reachable states
for (int i = 0; i < 8; i++) {
x = t.x + dx[i];
y = t.y + dy[i];
// If reachable state is not yet visited and
// inside board, push that state into queue
if (isInside(x, y, N) && !visit[x, y]) {
visit[x, y] = true;
q.Enqueue(new cell(x, y, t.dis + 1));
}
}
}
return int.MaxValue;
}
// Driver code
public static void Main(String[] args)
{
int N = 30;
int[] knightPos = { 1, 1 };
int[] targetPos = { 30, 30 };
Console.WriteLine(
minStepToReachTarget(
knightPos,
targetPos, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find minimum steps to reach to
// specific cell in minimum moves by Knight
// Class for storing a cell's data
class cell
{
constructor(x,y,dis)
{
this.x = x;
this.y = y;
this.dis = dis;
}
}
// Utility method returns true if (x, y) lies
// inside Board
function isInside(x,y,N)
{
if (x >= 1 && x <= N && y >= 1 && y <= N)
return true;
return false;
}
// Method returns minimum step
// to reach target position
function minStepToReachTarget(knightPos,targetPos,N)
{
// x and y direction, where a knight can move
let dx = [ -2, -1, 1, 2, -2, -1, 1, 2 ];
let dy = [ -1, -2, -2, -1, 1, 2, 2, 1 ];
// queue for storing states of knight in board
let q = [];
// push starting position of knight with 0 distance
q.push(new cell(knightPos[0], knightPos[1], 0));
let t;
let x, y;
let visit = new Array(N + 1);
// make all cell unvisited
for (let i = 1; i <= N; i++)
{
visit[i]=new Array(N+1);
for (let j = 1; j <= N; j++)
visit[i][j] = false;
}
// visit starting state
visit[knightPos[0]][knightPos[1]] = true;
// loop until we have one element in queue
while (q.length!=0) {
t = q.shift();
// if current cell is equal to target cell,
// return its distance
if (t.x == targetPos[0] && t.y == targetPos[1])
return t.dis;
// loop for all reachable states
for (let i = 0; i < 8; i++) {
x = t.x + dx[i];
y = t.y + dy[i];
// If reachable state is not yet visited and
// inside board, push that state into queue
if (isInside(x, y, N) && !visit[x][y]) {
visit[x][y] = true;
q.push(new cell(x, y, t.dis + 1));
}
}
}
return Number.MAX_VALUE;
}
// Driver code
let N = 30;
let knightPos=[1,1];
let targetPos=[30,30];
document.write(
minStepToReachTarget(
knightPos, targetPos, N));
// This code is contributed by rag2127
</script>
Producción:
20
Análisis de Complejidad:
- Complejidad del tiempo: O(N^2).
En el peor de los casos, se visitarán todas las celdas, por lo que la complejidad del tiempo es O (N ^ 2). - Espacio auxiliar: O(N^2).
Los Nodes se almacenan en cola. Entonces la Complejidad del espacio es O(N^2).
Este artículo es una contribución de Utkarsh Trivedi . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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