kürzester Weg im zweidimensionalen Array mit C

Question

Ich möchte einen kürzesten Weg von (0,0) zu (6,6) finden, aber ich weiß nicht, wie man es mit C macht. -1 ist die Art, wie ich kann gehen, und -2 ist die Art, wie ich nicht gehen kann. 0 ist Startpunkt und -3 ist Endpunkt. Bitte helfen ..

#include<stdio.h> 

#define VERTICES 7 

int maze[VERTICES][VERTICES] = { 
{ 0, -2, -1, -1, -1, -1, -1 }, 
{ -1, -2, -1, -2, -2, -2, -2 }, 
{ -1, -1, -1, -1, -1, -1, -1 }, 
{ -1, -2, -2, -2, -2, -2, -1 }, 
{ -1, -2, -1, -1, -1, -2, -1 }, 
{ -1, -2, -1, -2, -2, -2, -1 }, 
{ -1, -1, -1, -2, -1, -1, -3 } }; 

int A[VERTICES][VERTICES]; 

printA(int n) 
{ 
int i, j; 
printf("===============================\n"); 
for (i = 0; i < n; i++){ 
    for (j = 0; j < n; j++) 
     printf("%3d", A[i][j]); 
    printf("\n"); 
} 
printf("===============================\n"); 
} 
void solve(int n) 
{ 
int i, j, k=0; 
for (i = 0; i<n; i++) 
    for (j = 0; j<n; j++) 
     A[i][j] = maze[i][j]; 

while (1) 
{ 
    for (i = 0; i < n; i++) 
    { 
     for (j = 0; j < n; j++) 
      if (A[i][j] == k) 
      { 
       if (0 <= i + 1 < n && 0 <= j < n && A[i + 1][j] == -1) 
        A[i + 1][j] = k + 1; 
       if (0 <= i - 1 < n && 0 <= j < n && A[i - 1][j] == -1) 
        A[i - 1][j] = k + 1; 
       if (0 <= i < n && 0 <= j + 1 < n && A[i][j + 1] == -1) 
        A[i][j + 1] = k + 1; 
       if (0 <= i < n && 0 <= j - 1 < n && A[i][j - 1] == -1) 
        A[i][j - 1] = k + 1; 
       if (A[i][j] == -3) 
        break; 
      } 
    } 
    k++; 
} 
printf("%d\n", k); 
printA(VERTICES); 
} 

main() 
{ 
solve(VERTICES); 
} 

Answer 1

Ich weiß, sollte dies ein commend sein, aber ich .. genug Ruf haben nicht Anyways:

Sie auch für die a * (a-Stern) Algorithmus aussehen könnte Ihr Problem lösen dort Haufen von Implementierungen und Beschreibungen verfügbar sind zB:

http://code.activestate.com/recipes/577457-a-star-shortest-path-algorithm/

http://www.codeproject.com/Articles/9880/Very-simple-A-algorithm-implementation

heyes-jones.com/astar.php

Answer 2

Wie Jan Raufelder vorgeschlagen hat, könnten Sie den A * -Algorithmus verwenden, der als der beste Kompromiss zwischen Schnelligkeit und Genauigkeit gilt und in Videospielen weit verbreitet ist. Es gibt jedoch Fälle, in denen A * nach relativ langer Zeit den kürzesten Weg liefert, und diese Worst-Case-Szenarien erscheinen meistens für Labyrinthe.

███████████████████████ In this case, 
██ S  1 ██ E ██ A* will start at S, 
██ █████████████ ██ explore branch 1, 
██   2 ██ ██ then branch 2, 
██ █████████████ ██ and then branch 3, 
██   3 ██ ██ before taking branch 4 
██ █████████████ ██ to finally get to E. 
██   4  ██ It still gives you the shortest path, 
███████████████████████ but it takes a huge time. 

Wenn Sie eine robustere und in der Regel schnellere Lösung wollen, könnten Sie versuchen, Ihr Labyrinth in einem Graphen (Ecken und Kanten) zu konvertieren, und einen Dijkstra-Algorithmus auf sie anwenden. Aber das bedeutet, dass Sie alles, was Sie bisher gemacht haben, wiederholen und sich etwas Zeit nehmen, um darüber nachzudenken, wie Sie Ihr Labyrinth im Gedächtnis aufbauen, denn es wird nicht einfach ein 2D-Array von int sein.