Dado un tablero de ajedrez NxN y un Caballo en la posición (x,y). El Caballero tiene que dar exactamente K pasos, donde en cada paso elige cualquiera de las 8 direcciones uniformemente al azar. ¿Cuál es la probabilidad de que el caballo permanezca en el tablero después de dar K pasos, con la condición de que no pueda volver a entrar en el tablero una vez que lo abandone?
Ejemplos:
Let's take: 8x8 chessboard, initial position of the knight : (0, 0), number of steps : 1 At each step, the Knight has 8 different positions to choose from. If it starts from (0, 0), after taking one step it will lie inside the board only at 2 out of 8 positions, and will lie outside at other positions. So, the probability is 2/8 = 0.25
Acercarse:
Una cosa que podemos observar es que en cada paso el Caballero tiene 8 opciones para elegir. Supongamos que el Caballero tiene que dar k pasos y después de dar el K-ésimo paso el caballo alcanza (x,y). Hay 8 posiciones diferentes desde donde el caballo puede llegar a (x,y) en un solo paso, y son: (x+1,y+2), (x+2,y+1), (x+2, y-1), (x+1,y-2), (x-1,y-2), (x-2,y-1), (x-2,y+1), (x-1, y+2).
¿Qué pasaría si ya supiéramos las probabilidades de alcanzar estas 8 posiciones después de los pasos K-1?
Entonces, la probabilidad final después de K pasos será simplemente igual a (Σ probabilidad de alcanzar cada una de estas 8 posiciones después de K-1 pasos)/8;
Aquí estamos dividiendo por 8 porque cada una de estas 8 posiciones tiene 8 opciones y la posición (x,y) es una de las opciones.
Para las posiciones que se encuentran fuera del tablero, tomaremos sus probabilidades como 0 o simplemente las despreciaremos.
Dado que necesitamos realizar un seguimiento de las probabilidades en cada posición para cada número de pasos, necesitamos Programación Dinámica para resolver este problema.
Vamos a tomar una array dp[x][y][pasos] que almacenará la probabilidad de alcanzar (x,y) después de (pasos) el número de movimientos.
Caso base: si el número de pasos es 0, entonces la probabilidad de que el Caballo permanezca dentro del tablero es 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the probability of the
// Knight to remain inside the chessboard after
// taking exactly K number of steps
#include <bits/stdc++.h>
using namespace std;
// size of the chessboard
#define N 8
// direction vector for the Knight
int dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
// returns true if the knight is inside the chessboard
bool inside(int x, int y)
{
return (x >= 0 and x < N and y >= 0 and y < N);
}
// Bottom up approach for finding the probability to
// go out of chessboard.
double findProb(int start_x, int start_y, int steps)
{
// dp array
double dp1[N][N][steps + 1];
// for 0 number of steps, each position
// will have probability 1
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
dp1[i][j][0] = 1;
// for every number of steps s
for (int s = 1; s <= steps; ++s) {
// for every position (x,y) after
// s number of steps
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
double prob = 0.0;
// for every position reachable from (x,y)
for (int i = 0; i < 8; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// if this position lie inside the board
if (inside(nx, ny))
prob += dp1[nx][ny][s - 1] / 8.0;
}
// store the result
dp1[x][y][s] = prob;
}
}
}
// return the result
return dp1[start_x][start_y][steps];
}
// Driver Code
int main()
{
// number of steps
int K = 3;
// Function Call
cout << findProb(0, 0, K) << endl;
return 0;
}
Java
// Java program to find the probability
// of the Knight to remain inside the
// chessboard after taking exactly K
// number of steps
class GFG {
// size of the chessboard
static final int N = 8;
// direction vector for the Knight
static int dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
static int dy[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
// returns true if the knight is
// inside the chessboard
static boolean inside(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
// Bottom up approach for finding
// the probability to go out of
// chessboard.
static double findProb(int start_x, int start_y,
int steps)
{
// dp array
double dp1[][][] = new double[N][N][steps + 1];
// for 0 number of steps, each position
// will have probability 1
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
dp1[i][j][0] = 1;
// for every number of steps s
for (int s = 1; s <= steps; ++s) {
// for every position (x, y) after
// s number of steps
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
double prob = 0.0;
// for every position reachable
// from (x, y)
for (int i = 0; i < 8; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// if this position lie
// inside the board
if (inside(nx, ny))
prob
+= dp1[nx][ny][s - 1] / 8.0;
}
// store the result
dp1[x][y][s] = prob;
}
}
}
// return the result
return dp1[start_x][start_y][steps];
}
// Driver code
public static void main(String[] args)
{
// number of steps
int K = 3;
// Function Call
System.out.println(findProb(0, 0, K));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find the probability of # the Knight to remain inside the chessboard # after taking exactly K number of steps # size of the chessboard N = 8 # Direction vector for the Knight dx = [1, 2, 2, 1, -1, -2, -2, -1] dy = [2, 1, -1, -2, -2, -1, 1, 2] # returns true if the knight # is inside the chessboard def inside(x, y): return (x >= 0 and x < N and y >= 0 and y < N) # Bottom up approach for finding the # probability to go out of chessboard. def findProb(start_x, start_y, steps): # dp array dp1 = [[[0 for i in range(N+5)] for j in range(N+5)] for k in range(steps + 5)] # For 0 number of steps, each # position will have probability 1 for i in range(N): for j in range(N): dp1[i][j][0] = 1 # for every number of steps s for s in range(1, steps + 1): # for every position (x,y) after # s number of steps for x in range(N): for y in range(N): prob = 0.0 # For every position reachable from (x,y) for i in range(8): nx = x + dx[i] ny = y + dy[i] # if this position lie inside the board if (inside(nx, ny)): prob += dp1[nx][ny][s-1] / 8.0 # store the result dp1[x][y][s] = prob # return the result return dp1[start_x][start_y][steps] # Driver code # number of steps K = 3 # Function Call print(findProb(0, 0, K)) # This code is contributed by Anant Agarwal.
C#
// C# program to find the
// probability of the Knight
// to remain inside the
// chessboard after taking
// exactly K number of steps
using System;
class GFG {
// size of the chessboard
static int N = 8;
// direction vector
// for the Knight
static int[] dx = { 1, 2, 2, 1, -1, -2, -2, -1 };
static int[] dy = { 2, 1, -1, -2, -2, -1, 1, 2 };
// returns true if the
// knight is inside the
// chessboard
static bool inside(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
// Bottom up approach for
// finding the probability
// to go out of chessboard.
static double findProb(int start_x, int start_y,
int steps)
{
// dp array
double[, , ] dp1 = new double[N, N, steps+1];
// for 0 number of steps,
// each position will have
// probability 1
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
dp1[i, j, 0] = 1;
// for every number
// of steps s
for (int s = 1; s <= steps; ++s) {
// for every position (x, y)
// after s number of steps
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
double prob = 0.0;
// for every position
// reachable from (x, y)
for (int i = 0; i < 8; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// if this position lie
// inside the board
if (inside(nx, ny))
prob
+= dp1[nx, ny, s - 1] / 8.0;
}
// store the result
dp1[x, y, s] = prob;
}
}
}
// return the result
return dp1[start_x, start_y, steps];
}
// Driver code
static void Main()
{
// number of steps
int K = 3;
// Function Call
Console.WriteLine(findProb(0, 0, K));
}
}
// This code is contributed
// by Sam007
PHP
<?php
// PHP program to find the probability
// of the Knight to remain inside the
// chessboard after taking exactly K
// number of steps
// size of the chessboard
$N = 8;
// direction vector for the Knight
$dx = array(1, 2, 2, 1, -1, -2, -2, -1 );
$dy = array(2, 1, -1, -2, -2, -1, 1, 2 );
// returns true if the knight is
// inside the chessboard
function inside($x, $y)
{
global $N;
return ($x >= 0 and $x < $N and
$y >= 0 and $y < $N);
}
// Bottom up approach for finding the
// probability to go out of chessboard.
function findProb($start_x, $start_y, $steps)
{
global $N, $dx, $dy;
// dp array
$dp1 = array_fill(0, $N,
array_fill(0, $N,
array_fill(0, $steps+1, NULL)));
// for 0 number of steps, each
// position will have probability 1
for ($i = 0; $i < $N; ++$i)
for ($j = 0; $j < $N; ++$j)
$dp1[$i][$j][0] = 1;
// for every number of steps s
for ($s = 1; $s <= $steps; ++$s)
{
// for every position (x,y) after
// s number of steps
for ($x = 0; $x < $N; ++$x)
{
for ($y = 0; $y < $N; ++$y)
{
$prob = 0.0;
// for every position
// reachable from (x,y)
for ($i = 0; $i < 8; ++$i)
{
$nx = $x + $dx[$i];
$ny = $y + $dy[$i];
// if this position lie inside
// the board
if (inside($nx, $ny))
$prob += $dp1[$nx][$ny][$s - 1] / 8.0;
}
// store the result
$dp1[$x][$y][$s] = $prob;
}
}
}
// return the result
return $dp1[$start_x][$start_y][$steps];
}
// Driver Code
// number of steps
$K = 3;
// Function Call
echo findProb(0, 0, $K) . "\n";
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to find the probability
// of the Knight to remain inside the
// chessboard after taking exactly K
// number of steps
// size of the chessboard
let N = 8;
// direction vector for the Knight
let dx = [ 1, 2, 2, 1, -1, -2, -2, -1 ];
let dy = [2, 1, -1, -2, -2, -1, 1, 2];
// returns true if the knight is
// inside the chessboard
function inside(x,y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
// Bottom up approach for finding
// the probability to go out of
// chessboard.
function findProb(start_x, start_y, steps)
{
// dp array
let dp1 = new Array(N);
for(let i = 0; i < N; i++)
{
dp1[i] = new Array(N);
for(let j = 0; j < N; j++)
{
dp1[i][j] = new Array(steps + 1);
for(let k = 0; k < steps + 1; k++)
{
dp1[i][j][k] = 0;
}
}
}
// for 0 number of steps, each position
// will have probability 1
for (let i = 0; i < N; ++i)
for (let j = 0; j < N; ++j)
dp1[i][j][0] = 1;
// for every number of steps s
for (let s = 1; s <= steps; ++s)
{
// for every position (x, y) after
// s number of steps
for (let x = 0; x < N; ++x)
{
for (let y = 0; y < N; ++y)
{
let prob = 0.0;
// for every position reachable
// from (x, y)
for (let i = 0; i < 8; ++i)
{
let nx = x + dx[i];
let ny = y + dy[i];
// if this position lie
// inside the board
if (inside(nx, ny))
prob
+= dp1[nx][ny][s - 1] / 8.0;
}
// store the result
dp1[x][y][s] = prob;
}
}
}
// return the result
return dp1[start_x][start_y][steps];
}
// Driver code
// number of steps
let K = 3;
// Function Call
document.write(findProb(0, 0, K));
// This code is contributed by rag2127
</script>
0.125
Complejidad de tiempo : O(NxNxKx8) que es O(NxNxK), donde N es el tamaño del tablero y K es el número de pasos.
Complejidad espacial : O(NxNxK)
Este artículo es una contribución de Avinash Kumar Saw . 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