Herramientas de usuario

Herramientas del sitio


algoritmos-oia:grafos:bfs:distintas-movidas-en-tablero

¡Esta es una revisión vieja del documento!


Si en vez de ir a casillas adyacentes, hay distintos movimientos?

Algo que es muy común es tener distintos tipos de movimientos más allá de ir a casillas adyacentes en un tablero. El ejemplo más típico es el movimiento del caballo en el ajedrez.

Un caballo puede moverse a otra casilla si el “camino” de casillas adyacentes para ir de una a la otra forma una L, donde el palito largo de la L tiene 3 casillas y el corto tiene 2, como se ve en la siguiente figura:

Entonces, lo que vamos a hacer, es guardar en dos vectores, cuánto nos movemos en la dirección vertical y cuánto en la vertical, respectivamente. Es decir, vamos a tener vectores dx y dy que en la posición i-ésima guarden cuántos nos movemos en x y cuánto en y, respectivamente (en general, el eje x será el vertical, el de la primera coordenada en un vector de vectores). Y para simular las movidas desde la posición (a,b), haremos un for para cada movida i e iremos a la posición (a+dx[i],b+dy[i]) del tablero, siempre y cuando no nos hayamos ido del límite del tablero.

Para el movimiento mencionado del caballo, empezando por el de “arriba a la derecha”, los vectores quedarían:

vector<int> dx = {-2, -1, 1, 2, 2, 1, -1, -2}
vector<int> dy = {1, 2, 2, 1, -1, -2, -2, -1}

Problemas para practicar

algoritmos-oia/grafos/bfs/distintas-movidas-en-tablero.1514380743.txt.gz · Última modificación: 2017/12/27 13:19 por sebach