Hola , Tachicomaia, entiendo que quieres unir 2 puntos pintando la
menor cantidad posible de cuadraditos que compartan un vértice o un lado con otro contiguo.
En el primer caso cuando vas por una diagonal, es fácil hallar la fórmula , pero cuando la cantidad de cuadrados en vertical es diferente al horizontal , ya no hay un único camino, y allí debes escoger por el que te interesa, cuanto más grande es el cuadrado original y mas alejados estén los cuadrados inicial y final de una vertical horizontal y diagonal. mas variantes de caminos podras tener, Solo tu debes decidir cual es el camino que escoges de algún modo que te plazca,lo que si es seguro que dicho camino mas corto esta compuesto de dos partes , una serie de uniones en diagonal o otra serie de uniones en vertical u horizontal, pero nunca de ambas a la vez, sino el camino no es optimo en longitud.
Entonces el camino tienes que dividirlo en una cantidad de porciones diagonales contiguas y otra porción de uniones verticales u horizontales contiguas, la cantidad de caminos posibles sale de un numero combinatorio en base a esas cantidades, todos son posibles y óptimos en longitud, así que la formula dependerá de como quieras trazar ese camino.
para B hasta a 2 tienes dos formas de hacerlo, primero bajar uno en diagonal derecha y luego bajar en vertical, o primero bajar en vertical y luego bajar en diagonal a la derecha.
- ir a derecha es sumar 1 al numero anterior
- ir abajo es sumar $$n$$ (numero de cuadrados por lado del cuadrado grande) al número de cuadrado anterior
- diagonal hacia abajo y derecha es combinar ambos así que sumas $$n+1$$
retroceder o subir, es aplicar resta donde tienes sumas.
Así que todas las 8 posibles continuaciones de un camino las tienes contempladas con esas 3 indicaciones.
Spoiler
1) ir para arriba$$\to n_f=n_i-n$$
2) ir para arriba derecha $$\to n_f=n_i-n+1$$
3) ir para derecha $$\to n_f=n_i+1$$
4) ir para abajo derecha $$\to n_f=n_i+n+1$$
5) ir para abajo $$\to n_f=n_i+n$$
6) ir para abajo izquierda $$\to n_f=n_i+n-1$$
7) ir para izquierda $$\to n_f=n_i-1$$
8) ir para arriba izquierda$$\to n_f=n_i-n-1$$
Pero lo que te dice cual es la dirección del camino , la debes decidir previamente,
Te doy un ejemplo, puedes escojer primero siempre moverte en diagonal, hasta que el último cuadrado esté en la misma columna o fila que el el número final y luego ascender o bajar por la columna o bien retroceder o avanzar por las filas, eso sería una forma válida, pero también es válido todo lo contrario, moverse vertical u horizontal hasta la diagonal mas cercana y luego recorrerla... pero siempre es una elección entre estas dos variantes y de un montón mas de combinaciones posibles según el caso.
Los caminos que no tienen variantes, es decir una única forma de recorrerlos son los que están en la misma fila, columna o diagonal.
el número de caminos posibles son :
si $$df =\sqrt{(fila_{ final}-fila_{inicial})^2}$$
y si $$dc =\sqrt{(columna_{ final}-columna_{inicial})^2}$$
la longitud del camino es $$L=maximo(df,dc)$$
$$N=\binom{df}{dc}=\dfrac{df!}{dc!(df-dc)!}$$
$$N =\binom{dc}{df}=\dfrac{dc!}{df!(dc-df)!}$$
donde $$!$$ indica factorial de la variable previa.
Cualquiera que tomes de los $$N$$ caminos sera correcto
Si $$dc$$ o $$df$$ son 0 entonces el en número de caminos es 1 (comparten la vertical o la horizontal) lo mismo si $$df=dc$$ entonces $$N$$ es igual a 1 pues estas en una diagonal.
