OIA-Wiki

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 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:

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<int> dx = {-2, -1, 1, 2,  2,  1, -1, -2};
vector<int> dy = { 1,  2, 2, 1, -1, -2, -2, -1};

Caballo con movimientos extraños