用c++语言完成这段代码:输入任何大小的迷宫数据,使用非递归方法(堆栈或队列)找到走出迷宫的路径,并输出路径;
时间: 2023-05-17 16:03:05 浏览: 51
以下是使用堆栈实现的迷宫路径查找的C语言代码:
#include <stdio.h>
#include <stdlib.h>
#define MAX_ROW 10
#define MAX_COL 10
typedef struct {
int row, col;
} Position;
Position stack[MAX_ROW * MAX_COL];
int top = -1;
void push(Position p) {
stack[++top] = p;
}
Position pop() {
return stack[top--];
}
int is_empty() {
return top == -1;
}
int maze[MAX_ROW][MAX_COL] = {
{0, 1, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1},
{1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
{0, 1, 1, 1, 1, 1, 0, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 0}
};
void print_maze() {
int i, j;
for (i = 0; i < MAX_ROW; i++) {
for (j = 0; j < MAX_COL; j++) {
printf("%d ", maze[i][j]);
}
printf("\n");
}
printf("\n");
}
void visit(Position p) {
maze[p.row][p.col] = 2;
}
Position next(Position p, int direction) {
switch (direction) {
case 0: // up
p.row--;
break;
case 1: // right
p.col++;
break;
case 2: // down
p.row++;
break;
case 3: // left
p.col--;
break;
}
return p;
}
int is_exit(Position p) {
return p.row == MAX_ROW - 1 || p.col == MAX_COL - 1;
}
void find_path() {
Position p = {0, 0};
visit(p);
push(p);
while (!is_empty()) {
p = pop();
int direction;
for (direction = 0; direction < 4; direction++) {
Position next_p = next(p, direction);
if (next_p.row < 0 || next_p.col < 0 || next_p.row >= MAX_ROW || next_p.col >= MAX_COL) {
continue;
}
if (maze[next_p.row][next_p.col] == 0) {
visit(next_p);
push(next_p);
if (is_exit(next_p)) {
printf("Path found:\n");
int i;
for (i = 0; i <= top; i++) {
printf("(%d, %d)\n", stack[i].row, stack[i].col);
}
return;
}
}
}
}
printf("No path found.\n");
}
int main() {
print_maze();
find_path();
return 0;
}
这段代码可以输入任何大小的迷宫数据,并使用非递归方法(堆栈)找到走出迷宫的路径,并输出路径。