#include <stdio.h>
char matrix[8][8];
struct coordinate {
int a;
int b;
};
void ReadFile() {
printf("\n\n\n START MAZE ");
int x, y;
FILE * file1;
file1 = fopen("NEWmaze.txt", "r");
for (x = 0; x < 8; x ) {
for (y = 0; y < 8; y ) {
fscanf(file1, " %c", & matrix[x][y]);
}
printf("\n");
}
}
void PrintMaze() {
int x, y;
for (x = 0; x < 8; x ) {
printf(" ");
for (y = 0; y < 8; y ) {
printf(" %c ", matrix[x][y]);
}
printf("\n");
}
printf("\n\n\n\n");
}
struct coordinate DFS(int x, int y) {
struct coordinate retval = {
x,
y
};
printf("%c", matrix[x - 1][y]); //saw the target but could not stop
if (matrix[x][y - 1] == '-') //WEST
{
printf("WEST");
// printf("%d %d",x,y-1); step by step
matrix[x][y - 1] = '.';
PrintMaze(); //step by step
DFS(x, y - 1);
struct coordinate retval = {
x,
y - 1
};
}
if (matrix[x][y - 2] == 'g' && matrix[x 1][y - 2] != '#') {
// printf("%d %d ",x,y-2); step by step
return retval;
}
if (matrix[x - 1][y] == '-') //NORTH
{
// printf("%d %d",x-1,y); step by step
matrix[x - 1][y] = '.';
PrintMaze(); //step by step
DFS(x - 1, y);
struct coordinate retval = {
x - 1,
y
};
}
if (matrix[x - 2][y] == 'g' && matrix[x - 3][y] != '#') {
struct coordinate retval = {
0,
0
};
return retval;
}
if (matrix[x][y 1] == '-') //SOUTH
{
//printf("%d %d",x,y 1); step by step
matrix[x][y 1] = '.';
PrintMaze();
DFS(x, y 1);
struct coordinate retval = {
x,
y 1
};
}
if (matrix[x 1][y 1] == 'g' && matrix[x 2][y 1] != '#') {
struct coordinate retval = {
0,
0
};
return retval;
}
if (matrix[x 1][y] == '-') { // EAST
// printf("%d %d",x 1,y);
matrix[x 1][y] = '.';
//PrintMaze();
DFS(x 1, y);
struct coordinate retval = {
x 1,
y
};
}
if (matrix[x 1][y 1] == 'g' && matrix[x 1][y 2] != '#') {
struct coordinate retval = {
0,
0
};
return retval;
}
return retval;
}
void StartSearch() {
printf(" STEP BY STEP");
int x, y;
for (x = 0; x < 8; x ) {
for (y = 0; y < 8; y ) {
if (matrix[x][y] == 's') //START
{
struct coordinate coord = DFS(x, y);
}
}
printf("\n");
}
}
int main() {
ReadFile();
PrintMaze();
StartSearch();
PrintMaze();
return 0;
}
newMaze.txt 檔案 (# wall, . step, - empty , s start,g goal)
# # # # # # # #
# g - - # - - #
# - - - - - # #
# - - # - - - #
# - - # - - # #
# - - - - - - #
# - # - - - s #
# # # # # # # #
我列印了這些步驟，我可以看到它達到了目標。唯一的問題是當我達到目標時它不會停止（'g'）。當我使用 while break 時，它無法擺脫無限回圈。當它達到目標（'g'）時，我如何讓它停止？
這是對 -> 的后續行動
更新
#include <stdio.h> char matrix[8][8]; struct coordinate { int x, y; }; void ReadFile() { printf("\n\n\n START MAZE "); int x,y; FILE *file1; file1=fopen("NEWmaze.txt","r"); for(x=0; x<8; x ){ for(y=0;y<8;y ) { fscanf (file1, " %c", &matrix[x][y]); } printf("\n"); } } void PrintMaze() { int x,y; for(x=0;x<8;x ) { printf(" "); for(y=0;y<8;y ) { printf(" %c ",matrix[x][y]); } printf("\n"); } printf("\n\n\n\n"); } struct coordinate DFS(int x, int y) { struct coordinate retval = { -1, -1 }; if (matrix[x][y] == 'g') { retval.x = x; retval.y = y; } else if (matrix[x][y] == '-' ) { matrix[x][y] = 'o';// West North South East PrintMaze(); retval = DFS(x, y-1); if (retval.x != -1) return retval; retval = DFS(x-1, y ); if (retval.x != -1) return retval; retval = DFS(x , y 1); if (retval.x != -1) return retval; retval = DFS(x 1, y); matrix[x][y] = '.'; } return retval; } void StartSearch() { printf(" STEP BY STEP"); int x,y; for(x=0;x<8;x ) { for(y=0;y<8;y ) { if(matrix[x][y] == 's')//START { if(matrix[x][y-1] == '-') { DFS(x,y-1); } if(matrix[x-1][y] == '-') { DFS(x-1,y); } if(matrix[x][y 1] == '-') { DFS(x,y 1); } if(matrix[x 1][y] == '-') { DFS(x 1,y); } } } printf("\n"); } } int main() { ReadFile(); PrintMaze(); StartSearch(); PrintMaze(); return 0; }更新輸出
我按優先順序寫了，它有效。
uj5u.com熱心網友回復：
您正在以一種奇怪的方式處理回傳值。與其在遞回呼叫之后構造它，不如簡單地讓它回傳一個有效的坐標，如果當前位置是目標。否則，回傳無效的東西（例如{-1,-1}，或者在你的情況下甚至是 {0,0}，如果那總是一堵墻）。
現在您需要做的就是存盤每個遞回呼叫的回傳值并檢查它是否有效。如果是，則立即退回。否則繼續處理（即測驗其他方向）。
就代碼而言，如下所示：
struct coordinate { int x, y; }; struct coordinate DFS(int x, int y) { struct coordinate retval = { -1, -1 }; if (matrix[x][y] == 'g') { retval.x = x; retval.y = y; } else if (matrix[x][y] == '-' || matrix[x][y] == 's') { matrix[x][y] = '.'; retval = DFS(x - 1, y); if (retval.x != -1) return retval; retval = DFS(x, y - 1); if (retval.x != -1) return retval; retval = DFS(x 1, y); if (retval.x != -1) return retval; retval = DFS(x, y 1); } return retval; }如果你的迷宮總是在外圍有一堵墻，你就不需要對坐標做任何邊界測驗，因為你永遠不會在邊緣執行遞回。
您甚至可以稍微重新排序以繪制第一次到達目標時使用的實際路徑。它可能不是最佳路徑，但這需要更高級的演算法。下面，我們用它
'o'來表示通往目標的路徑上的一個單元格。struct coordinate DFS(int x, int y) { struct coordinate retval = { -1, -1 }; if (matrix[x][y] == 'g') { retval.x = x; retval.y = y; } else if (matrix[x][y] == '-' || matrix[x][y] == 's') { matrix[x][y] = '.'; retval = DFS(x - 1, y); if (retval.x == -1) retval = DFS(x, y - 1); if (retval.x == -1) retval = DFS(x 1, y); if (retval.x == -1) retval = DFS(x, y 1); if (retval.x != -1) matrix[x][y] = 'o'; } return retval; }并對搜索功能稍作調整：
void StartSearch() { int x, y; for (x = 0; x < 8; x ) { for (y = 0; y < 8; y ) { if (matrix[x][y] == 's') { DFS(x, y); matrix[x][y] = 's'; } } } }你得到這個輸出：
# # # # # # # # # g o o # . . # # - - o o o # # # - - # - o - # # - - # - o # # # - - - - o o # # - # - - - s # # # # # # # # #轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482727.html
下一篇：c Gomoku對角線檢查器
