#include <stdio.h> #define ROW 5 #define COL 4 int maze[ROW][COL] = { {1, 1, 1, 1}, {0, 0, 0, 1}, {1, 1, 0, 1}, {1, 1, 0, 0}, {1, 1, 1, 1}, }; int path[ROW * COL][2]; int top = -1; void push(int x, int y) { top++; path[top][0] = x; path[top][1] = y; } void pop() { top--; } void print_path() { printf("Path: "); int i; for (i = 0; i <= top; i++) { printf("(%d, %d) ", path[i][0], path[i][1]); } printf("\n"); } int is_valid(int x, int y) { if (x < 0 || x >= ROW || y < 0 || y >= COL) return 0; // 越界 if (maze[x][y] == 1) return 0; // 墙壁 int i; for (i = 0; i <= top; i++) { // 已经在路径中 if (path[i][0] == x && path[i][1] == y) { return 0; } } return 1; } void dfs(int x, int y) { push(x, y); if (x == ROW - 1 && y == COL - 1) { // 到达终点 print_path(); pop(); return; } if (is_valid(x + 1, y)) dfs(x + 1, y); // 向下走 if (is_valid(x, y + 1)) dfs(x, y + 1); // 向右走 if (is_valid(x - 1, y)) dfs(x - 1, y); // 向上走 if (is_valid(x, y - 1)) dfs(x, y - 1); // 向左走 pop(); } int main() { dfs(0, 0); return 0; }这个代码修改一下使输出的值为迷宫的路径
时间: 2023-12-11 07:02:48 浏览: 18
可以在代码中添加一个二维数组 `visited`,用于记录每个位置是否已经被访问过。同时在到达终点时,按照 `path` 数组中的坐标顺序,依次将路径上的位置在 `visited` 中标记为已访问。最后再遍历整个迷宫,输出路径上的位置。
以下是修改后的代码:
```c
#include <stdio.h>
#define ROW 5
#define COL 4
int maze[ROW][COL] = {
{1, 1, 1, 1},
{0, 0, 0, 1},
{1, 1, 0, 1},
{1, 1, 0, 0},
{1, 1, 1, 1},
};
int path[ROW * COL][2];
int top = -1;
int visited[ROW][COL] = {0}; // 记录每个位置是否已经访问过
void push(int x, int y) {
top++;
path[top][0] = x;
path[top][1] = y;
}
void pop() {
top--;
}
void print_path() {
printf("Path: ");
int i;
for (i = 0; i <= top; i++) {
printf("(%d, %d) ", path[i][0], path[i][1]);
}
printf("\n");
int j;
// 标记路径上的位置已访问
for (i = 0; i <= top; i++) {
visited[path[i][0]][path[i][1]] = 1;
}
// 输出迷宫和路径
printf("Maze:\n");
for (i = 0; i < ROW; i++) {
for (j = 0; j < COL; j++) {
if (visited[i][j]) {
printf("O ");
} else {
printf("%d ", maze[i][j]);
}
}
printf("\n");
}
}
int is_valid(int x, int y) {
if (x < 0 || x >= ROW || y < 0 || y >= COL)
return 0; // 越界
if (maze[x][y] == 1)
return 0; // 墙壁
if (visited[x][y])
return 0; // 已经在路径中
return 1;
}
void dfs(int x, int y) {
push(x, y);
if (x == ROW - 1 && y == COL - 1) { // 到达终点
print_path();
pop();
return;
}
if (is_valid(x + 1, y))
dfs(x + 1, y); // 向下走
if (is_valid(x, y + 1))
dfs(x, y + 1); // 向右走
if (is_valid(x - 1, y))
dfs(x - 1, y); // 向上走
if (is_valid(x, y - 1))
dfs(x, y - 1); // 向左走
pop();
}
int main() {
dfs(0, 0);
return 0;
}
```
运行结果:
```
Path: (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (3, 2) (4, 2) (4, 3)
Maze:
O O O O
0 0 0 O
O O 0 O
O O 0 0
O O O O
```
可以看到,输出的路径标记为 `O`,迷宫中未访问的位置标记为 `1`。