「波算法」（總部設在李的算法）用C

Question

我正在寫有值的程序計算從A點的最短途徑到B點。 我有一個地圖（矩陣）：

• 0是塊（牆，沒辦法通過）;
• 1是免費的方式（你可以通過）;
• 11是A點（起點）;
• 22是B點（終點）。

我讀過一些文章，它應該如何工作，並試圖實現我自己的版本，但堆積如山。

在下面的代碼中，我聲明瞭2個數組：在運行顯示訪問點的程序時，使用Map和更改數組「訪問」數組。

我在4個方向（不是對角線）上檢查單元格爲1或0.如果它是1（可能通過），我增加計數器爲1.因爲不計數以前的單元格，我試圖避免它由條件。

因此，我想用幾行顯示到達點B（1,2,3，... 15）的方式來看到「已訪問」矩陣。

現在我的地圖看起來不正確，甚至沒有接近。

我在算法中錯過了什麼，應該考慮什麼以及如何解決我的程序？

謝謝。

P.S.我寫了一些函數實現了一個新的數組，其值爲0，可以自由計算單元格和打印數組。

main.c中：

#include <stdbool.h> 
#include <stdlib.h> 
#include <stdio.h> 

#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 < HEIGHT; ++j) 
     { 
      if (((i >= 0) && (i < WIDTH)) && ((j >= 0) && (j < HEIGHT))) 
      { 
       // [i + 1][j] 
       if (map[i + 1][j] == 1) 
       { 
        map[i][j] = prevPosition; 
        if (prevPosition) 
         visited[i + 1][j] = count++; 

       } 
       if (map[i + 1][j] == 0) 
       { 
        visited[i + 1][j] = map[i + 1][j]; 
       } 

       // [i - 1][j] 
       if (map[i - 1][j] == 1) 
       { 
        map[i][j] = prevPosition; 
        if (prevPosition) 
         visited[i - 1][j] = count++; 
       } 
       if (map[i - 1][j] == 0) 
       { 
        visited[i - 1][j] = map[i - 1][j]; 
       } 

       // [i][j + 1] 
       if (map[i][j + 1] == 1) 
       { 
        map[i][j] = prevPosition; 
        if (prevPosition) 
         visited[i][j + 1] = count++; 
       } 
       if (map[i][j + 1] == 0) 
       { 
        visited[i][j + 1] = map[i][j + 1]; 
       } 

       // [i][j - 1] 
       if (map[i][j - 1] == 1) 
       { 
        map[i][j] = prevPosition; 
        visited[i][j - 1] = map[i][j - 1]; 
        if (prevPosition) 
         visited[i][j - 1] = count++; 
       } 
       if (map[i][j - 1] == 0) 
       { 
        visited[i][j - 1] = map[i][j - 1]; 
       } 

      } // map borders check (finished) 
       //count++; 
     } 
    } 

    printf("count: %d\n", count); 

    if (count > 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; 
} 

這裏最短的方式是總是15細胞

Answer 1

在main功能的嵌套循環，表達((i >= 0) && (i < WIDTH)) && ((j >= 0) && (j < HEIGHT))將總是是真實。

這意味着你將超出你的數組的界限。

我建議你檢查i的值作爲做​​。也許類似

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

如果你這樣做了，其他地方類似的還有（當你做i - 1檢查i > 0的），那麼你不應該去出界，並有未定義的行爲。

與上述檢查類似的另一種可能性是對i（或j）進行一次檢查，然後執行現在的檢查。像

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

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