OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
===== Ir a casillas vecinas =====

En muchos problemas, estamos en un tablero, y tenemos permitido movernos a casillas vecinas (a veces pueden estar bloqueadas y no se podrá entrar). Es decir, lo importante es que desde cualquier casilla, tenemos siempre **las mismas posibilidades de movimiento**: arriba, abajo, izquierda, derecha.
Habrá casos particulares de cuando estamos en un borde por ejemplo, no podremos salirnos del tablero.

Una primera manera de ir a las casillas vecinas de $(i, j)$, es, a mano, ver de ir a $(i+1, j)$, $(i-1, j)$, $(i, j+1)$, $(i, j-1)$.
En este caso es sencillo porque hay sólo cuatro posibles movimientos. Si en cambio pudiéramos movernos a una casilla con la que comparte un punto (las casillas con las que comparte una esquina), ya habría $8$ lugares a los cuales moverse.

Aunque haya pocas casillas vecinas, hacer cada movimiento por separado es más propenso a errores: a veces terminamos copiando y pegando código para repetir el accionar en cada vecino; ponemos un $+1$ en vez de un $-1$ y dejamos vecinos sin ver.
Pero además de los posibles errores, esta manera siempre nos hace escribir varias veces lo mismo.

¿Qué pasaba cuando teníamos menos conocimiento y hacíamos cosas más básicas, cuando queríamos hacer varias veces lo mismo? **FOR!**

La clave es, en un for, "movernos" por todos los vecinos. ¿Cómo? No es tan simple como un $for(vecino : vecinos)$ porque no tenemos una lista de vecinos. (Esto tiene que ver con tener un grafo de manera implícita, pueden leer un poco [[algoritmos-oia/grafos#representacion_en_la_computadora|acá]].)

Para hacer esto, podemos tener dos vectorcitos, $dx$ y $dy$, que en la posición $i$, los vectores nos digan que para ir al i-ésimo vecino debo moverme $dx[i]$ en la dirección $x$, y $dy[i]$ en la dirección $y$.

Para ir a las casillas vecinas como dijimos, tendríamos ''vector<int> dx = {1, -1, 0, 0};'' y ''vector<int> dy = {0, 0, 1, -1};''


** Y qué pasa si en vez de que las casillas vecinas sean las adyacentes, son otras? **

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:

{{ :algoritmos-oia:grafos:bfs:caballo-movimientos.jpeg?200 |}}

Entonces, lo que vamos a hacer, es usar la misma idea de los vectores $dx$ y $dy$, sólo que cambiando los elementos.
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" y siguiendo en sentido horario, los vectores quedarían:
<code cpp>
// incrementar en x significa ir a una fila mas abajo, incrementar y significa ir a una columna mas a la derecha
vector<int> dx = {-2, -1, 1, 2,  2,  1, -1, -2};
vector<int> dy = { 1,  2, 2, 1, -1, -2, -2, -1};
</code>

==== Problemas para practicar ====

[[https://www.hackerrank.com/contests/world-codesprint-12/challenges/red-knights-shortest-path|Caballo con movimientos extraños]]
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
