“Wave Algorithm” (basé sur l’algorithme de Lee) en C

J’écris un calcul de programme le plus court chemin du point A au point B. J’ai une carte (masortingce) avec des valeurs:

  • 0 est un bloc (mur, pas moyen de passer);
  • 1 est un moyen libre (vous pouvez passer);
  • 11 est le point A (sharepoint départ);
  • 22 est le point B (point d’arrivée).

J’ai lu quelques articles sur le fonctionnement normal et essayé de réaliser ma propre version mais je me suis empilé.

Dans le code ci-dessous, je déclare 2 tableaux: un tableau avec Map et le tableau modifié “visité” lors de l’exécution du programme présentant les points visités.

Je vérifie les cellules dans 4 directions (pas les diagonales) pour 1 ou 0. Si c’est 1 (possible de passer), j’augmente le compteur pour 1. Pour ne pas compter la cellule précédente, j’essaie de l’éviter par la condition.

En conséquence, je veux voir la masortingce “visité” avec quelques lignes indiquant le chemin pour atteindre le point B (1, 2, 3, … 15).

À l’heure actuelle, ma carte ne semble pas correcte, pas même proche.

Qu’est-ce que j’ai manqué dans mon algorithme, que dois-je prendre en compte et comment réparer mon programme?

Je vous remercie.

PS J’ai écrit quelques fonctions implémentant un nouveau tableau avec 0 valeurs, en comptant les cellules libres et les tableaux d’impression.

principal c:

#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("Masortingx of zeroed-visited cells:\n\n"); mapPrint(visited); printf("Masortingx 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("Masortingx 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; } 

Ici le chemin le plus court est toujours 15 cellules

entrez la description de l'image ici

Dans les boucles nestedes de la fonction main , l’expression ((i >= 0) && (i < WIDTH)) && ((j >= 0) && (j < HEIGHT)) sera toujours vraie.

Cela signifie que vous allez sortir des limites de vos tableaux.

Je vous suggère de vérifier la valeur de i lors de l'exécution de if (map[i + 1][j] == 1) par exemple, if (map[i + 1][j] == 1) . Peut-être quelque chose comme

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

Si vous faites la même chose pour les autres endroits (car quand vous faites i - 1 vérifiez i > 0 ), vous ne devriez pas sortir du cadre ni adopter un comportement indéfini .

Une autre possibilité similaire à la vérification ci-dessus consiste à avoir une vérification pour que i (ou j ) se trouve dans la plage, puis la vérification que vous avez maintenant. Quelque chose comme

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