===== 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 dx = {1, -1, 0, 0};'' y ''vector 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: // incrementar en x significa ir a una fila mas abajo, incrementar y significa ir a una columna mas a la derecha vector dx = {-2, -1, 1, 2, 2, 1, -1, -2}; vector dy = { 1, 2, 2, 1, -1, -2, -2, -1}; ==== Problemas para practicar ==== [[https://www.hackerrank.com/contests/world-codesprint-12/challenges/red-knights-shortest-path|Caballo con movimientos extraños]]