我需要用C編寫一個程序，遞歸地解決X和空格的迷宮問題

Question

程序必須從索引[0] [1]開始，並在索引[7] [7]時完成迷宮。該程序到達「FindPath」函數時崩潰。我想不出我做錯了什麼，任何信息都有幫助。

#include "Header.h" 

int main(void) { 

int x = 0, y = 1; 

char maze[8][8] = { 
{' ', ' ', 'x', 'x', 'x', 'x', 'x', 'x'}, 
{' ', 'x', 'x', 'x', 'x', 'x', 'x', 'x'}, 
{' ', 'x', 'x', 'x', 'x', 'x', 'x', 'x'}, 
{' ', ' ', ' ', ' ', ' ', 'x', 'x', 'x'}, 
{'x', 'x', 'x', 'x', ' ', 'x', 'x', 'x'}, 
{'x', 'x', 'x', 'x', ' ', ' ', ' ', ' '}, 
{'x', 'x', 'x', 'x', 'x', 'x', 'x', ' '}, 
{'x', 'x', 'x', 'x', 'x', 'x', 'x', ' '}, 
}; 

for (int i = 0; i < 8; i++) { 
    for (int j = 0; j < 8; j++) { 
     printf("%c ",maze[i][j]); 
    } 
     printf("\n"); 
} 


FindPath(maze, x, y); 

return 0; 
} 


#include "Header.h" 

void FindPath(char maze[8][8], int x, int y) { 

if (x == 7 & y == 7) { 
    printf("Maze complete"); 

    for (int i = 0; i < 8; i++) { 
     for (int j = 0; j < 8; j++) { 
      printf("%c ", maze[i][j]); 
     } 
     printf("\n"); 
    } 
     return; 
} 
else { 

    if (maze[x + 1][y] = ' ') { 
     maze[x][y] = 'h'; 
     FindPath(maze, x + 1, y); 
     return; 
    } 
    else if (maze[x - 1][y] = ' ') { 
     maze[x][y] = 'h'; 
     FindPath(maze, x - 1, y); 
     return; 
    } 
    else if (maze[x][y + 1] = ' ') { 
     maze[x][y] = 'h'; 
     FindPath(maze, x, y + 1); 
     return; 
    } 
    else if (maze[x][y - 1] = ' ') { 
     maze[x][y] = 'h'; 
     FindPath(maze, x, y - 1); 
     return; 
    } 
    else { 
     printf("no path found"); 
     return; 
    } 
} 
} 

Answer 1

我相信這個問題比你做得更簡單。

您的方法的主要問題：FindPath()需要在試驗和錯誤的基礎上工作 - 您沒有任何策略允許它成功和/或失敗併發出信號以表明它是調用者，也不會撤消它的錯誤假設。

問題與您的代碼：人們已經提到=與==，但你也可以使用&當你的意思是&&;您的代碼縮進或SO代碼發佈需要工作;你應該努力避免代碼中的數字，以便以後可以換出迷宮;您的較低級別的例程應該返回結果，而不是打印 - 您的較高級別例程應返回這些結果並決定要打印的內容;大量冗餘代碼 - 將重複的語句向上移動一級;正如其他人所提到的，您需要進行限制檢查，因爲maze[x - 1][y]等表達式可能會侵佔您未分配的內存，如果x爲零。

下面是你的代碼沿着上面的線條和一些風格的改變的返工。它解決了一個迷宮，你提供：

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

#define WIDTH (8) 
#define HEIGHT (8) 

void printMaze(char maze[WIDTH][HEIGHT]) { 

    for (int i = 0; i < WIDTH; i++) { 
      for (int j = 0; j < HEIGHT; j++) { 
        printf("%c ", maze[i][j]); 
     } 
     putchar('\n'); 
    } 
} 

bool findPath(char maze[WIDTH][HEIGHT], int x, int y) { 

    maze[x][y] = 'h'; 

    if (x == WIDTH - 1 && y == HEIGHT - 1) { 
     return true; 
    } 

    if (x + 1 < WIDTH && maze[x + 1][y] == ' ') { 
     if (findPath(maze, x + 1, y)) { 
      return true; 
     } 
    } 

    if (x - 1 >= 0 && maze[x - 1][y] == ' ') { 
     if (findPath(maze, x - 1, y)) { 
      return true; 
     } 
    } 

    if (y + 1 < HEIGHT && maze[x][y + 1] == ' ') { 
     if (findPath(maze, x, y + 1)) { 
      return true; 
     } 
    } 

    if (y - 1 >= 0 && maze[x][y - 1] == ' ') { 
     if (findPath(maze, x, y - 1)) { 
      return true; 
     } 
    } 

    maze[x][y] = ' '; 

    return false; 
} 

int main(void) { 

    char maze[WIDTH][HEIGHT] = { 
     {' ', ' ', 'x', 'x', 'x', 'x', 'x', 'x'}, 
     {' ', 'x', 'x', 'x', 'x', 'x', 'x', 'x'}, 
     {' ', 'x', 'x', 'x', 'x', 'x', 'x', 'x'}, 
     {' ', ' ', ' ', ' ', ' ', 'x', 'x', 'x'}, 
     {'x', 'x', 'x', 'x', ' ', 'x', 'x', 'x'}, 
     {'x', 'x', 'x', 'x', ' ', ' ', ' ', ' '}, 
     {'x', 'x', 'x', 'x', 'x', 'x', 'x', ' '}, 
     {'x', 'x', 'x', 'x', 'x', 'x', 'x', ' '}, 
    }; 

    printMaze(maze); 

    if (findPath(maze, 0, 1)) { 
     printf("Maze completed!\n"); 
     printMaze(maze); 
    } else { 
     printf("No path found!"); 
    } 

    return 0; 
} 

輸出

> ./a.out 
    x x x x x x 
    x x x x x x x 
    x x x x x x x 
      x x x 
x x x x x x x 
x x x x   
x x x x x x x 
x x x x x x x 
Maze completed! 
h h x x x x x x 
h x x x x x x x 
h x x x x x x x 
h h h h h x x x 
x x x x h x x x 
x x x x h h h h 
x x x x x x x h 
x x x x x x x h 
>