“Algoritmo de onda” (basado en el algoritmo de Lee) en C

Estoy escribiendo un progtwig de cálculo del camino más corto desde el punto A al punto B. Tengo un mapa (matriz) con valores:

  • 0 es bloque (muro, no hay forma de pasar);
  • 1 es de forma gratuita (puedes pasar);
  • 11 es el punto A (punto de inicio);
  • 22 es el punto B (punto final).

He leído algunos artículos sobre cómo debería funcionar y traté de realizar mi propia versión, pero me apilé.

En el código a continuación declaro 2 matrices: una matriz con Mapa y matriz modificada “visitada” mientras se ejecuta el progtwig que demuestra los puntos visitados.

Verifico las celdas en 4 direcciones (no en diagonales) para 1 o 0. Si es 1 (es posible pasar), aumente el contador para 1. Para no contar la celda anterior, estoy tratando de evitarla por la condición.

Como resultado, quiero ver una matriz “visitada” con unas pocas líneas que muestran la forma de llegar al punto B (1, 2, 3, … 15).

En este momento mi mapa no parece correcto, ni siquiera cerca.

¿Qué he perdido en mi algoritmo, qué debo tener en cuenta y cómo arreglar mi progtwig?

Gracias.

PS: escribí algunas funciones implementando una nueva matriz con valores 0, contando las celdas libres para imprimir y matrices de impresión.

C Principal:

#include  #include  #include  #define WIDTH 8 #define HEIGHT 8 int mapZero(int map[WIDTH][WIDTH]); int mapPrint(int map[WIDTH][HEIGHT]); int mapInit(int map[WIDTH][WIDTH]); int findFreeToGoCells(int map[WIDTH][WIDTH]); int main(int argc, char * argv[]) { short int prevPosition; short int currPosition; short int nextPosition; short int lastPosition; int visited[WIDTH][HEIGHT]; unsigned int count; unsigned int max; mapZero(visited); int map[WIDTH][HEIGHT] = { { 11, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 1, 1, 1, 1, 0, 1 }, { 0, 0, 1, 0, 1, 1, 1, 0 }, { 1, 0, 1, 1, 1, 0, 1, 1 }, { 0, 0, 0, 1, 0, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0, 0, 1 }, { 0, 0, 0, 0, 1, 0, 0, 1 }, { 0, 1, 1, 1, 1, 1, 1, 22 }, }; printf("Matrix of zeroed-visited cells:\n\n"); mapPrint(visited); printf("Matrix of the map:\n\n"); mapPrint(map); printf("Ways: %d\n", findFreeToGoCells(map)); prevPosition = map[0][0]; currPosition = 0; count = 0; max = WIDTH * HEIGHT; for (int i = 0; i < WIDTH; ++i) { for (int j = 0; j = 0) && (i = 0) && (j  1000) { printf("The way couldn't be found\n"); } else { printf("Matrix of visited cells:\n\n"); mapPrint(visited); //printf("Short way: %d\n", findShortWay(map[7][7])); } printf("Ways: %d\n", findFreeToGoCells(visited)); system("pause"); return 0; } int mapZero(int map[WIDTH][WIDTH]) { for (int i = 0; i < WIDTH; ++i) { for (int j = 0; j < HEIGHT; ++j) { map[i][j] = 0; } } } int mapPrint(int map[WIDTH][HEIGHT]) { for (int i = 0; i < WIDTH; ++i) { for (int j = 0; j < HEIGHT; ++j) { printf("%2d ", map[i][j]); } printf("\n\n"); } printf("\n"); return 0; } int findFreeToGoCells(int map[WIDTH][WIDTH]) { int count = 0; for (int i = 0; i < WIDTH; ++i) { for (int j = 0; j < HEIGHT; ++j) { if (map[i][j] == 1 || map[i][j] == 99) count++; } } return count; } 

Aquí el camino más corto es siempre 15 celdas.

introduzca la descripción de la imagen aquí

En los bucles nesteds en la función main , la expresión ((i >= 0) && (i < WIDTH)) && ((j >= 0) && (j < HEIGHT)) siempre será verdadera.

Eso significa que saldrás de los límites de tus arreglos.

Le sugiero que verifique el valor de i como parte de hacer, por ejemplo, if (map[i + 1][j] == 1) . Tal vez algo como

 if (i < WIDTH - 1 && map[i + 1][j] == 1) { ... } 

Si lo haces de manera similar para los otros lugares (para cuando hagas i - 1 comprueba i > 0 ), no debes salir de los límites y tener un comportamiento indefinido .

Otra posibilidad similar a la comprobación anterior es tener una comprobación para i (o j ) que esté dentro del rango y luego realizar la comprobación que tiene ahora. Sonar como

 if (i < WIDTH - 1) { if (map[i + 1][j] == 1) { ... } if (map[i + 1][j] == 0) { ... } }