C语言迷宫求解算法实现 - 使用栈数据结构

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

#define row 8 #define col 11

typedef struct { int x; int y; } Position;

typedef struct { int top; // 栈顶指针 Position *data; // 栈的数据 } Stack;

int map[row][col] = { {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1}, {1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1}, {1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1}, {1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1}, {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} }; // 迷宫地图，1代表墙壁，0代表路

int enterx = 1, entery = 1; // 入口坐标 int exitx = 6, exity = 9; // 出口坐标

typedef struct { Position position; // 当前位置 int direct; // 下一步的方向（1代表上，2代表右，3代表下，4代表左） } Path;

Path path[(row - 1) * (col - 1)]; // 探索迷宫的路径 int pathLength = 0; // 路径长度

void CreateStack(Stack *s, int size); void Push(Stack *s, Position elem); Position Pop(Stack *s); int IsEmpty(Stack *s); void Maze(Stack *s); void RecordExplorationPath(Position p); void PrintPath();

int main(int argc, char* argv[]) {

Stack L;
CreateStack(&L, row * col);

Maze(&L);

if (pathLength > 0) {
    PrintPath();
} else {
    printf('Can not find path');
}

return 0;

}

// 创建栈 void CreateStack(Stack s, int size) { s->top = -1; s->data = (Position)malloc(sizeof(Position) * size); }

// 入栈 void Push(Stack *s, Position elem) { s->top++; s->data[s->top] = elem; }

// 出栈 Position Pop(Stack *s) { Position elem = s->data[s->top]; s->top--; return elem; }

// 判断栈是否为空 int IsEmpty(Stack *s) { return s->top == -1; }

// 判断是否是走过的迷宫块 int Panduan(int x, int y) { if (map[x][y] == 0) { return 1; }

return 0;

}

// 探索迷宫可通行的路径 void Maze(Stack *s) { Position p; p.x = enterx; p.y = entery;

Push(s, p);
map[p.x][p.y] = 2;

while (!IsEmpty(s)) {
    p = Pop(s);
    RecordExplorationPath(p);

    if (p.x == exitx && p.y == exity) {
        return;
    }

    int x = p.x;
    int y = p.y;

    if (Panduan(x-1, y) && map[x-1][y] != 2) {
        Push(s, (Position){x-1, y}); // 上
        map[x-1][y] = 2;
    }
    if (Panduan(x, y+1) && map[x][y+1] != 2) {
        Push(s, (Position){x, y+1}); // 右
        map[x][y+1] = 2;
    }
    if (Panduan(x+1, y) && map[x+1][y] != 2) {
        Push(s, (Position){x+1, y}); // 下
        map[x+1][y] = 2;
    }
    if (Panduan(x, y-1) && map[x][y-1] != 2) {
        Push(s, (Position){x, y-1}); // 左
        map[x][y-1] = 2;
    }
}

}

// 记录探索路径 void RecordExplorationPath(Position p) { path[pathLength].position.x = p.x; path[pathLength].position.y = p.y; pathLength++; }

// 打印迷宫可通行的路径 void PrintPath(){ for (int i = 0; i < pathLength; i++) { printf('%d:(%d, %d)\n',path[i].position.x, path[i].position.y); } return;