• 日期: 2024-07-12
  • 标签: 常规

#include 'maze.h'

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; // 出口坐标

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

int main(int argc, char* argv[]) { LinkStack L; L.count = 0; CreateLink(&L);

bool flag = Maze(&L);
	
if (flag == true) {
	PrintPath();
} else {
	printf("Can not find path");
}

return 0;

}

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

return false;

}

// 探索迷宫可通行的路径 bool Maze(LinkStack* L) { bool flag = false;

LinkStackPtr p;
p = (LinkStackPtr)malloc(sizeof(struct StackNode));
p->position.x = enterx;
p->position.y = entery;
p->direct.top = 1;
p->direct.right = 0;
p->direct.left = 0;
p->direct.bottom = 0;
map[p->position.x][p->position.y] = 2;

// 将入口结点入栈
Push(L, p);

//
//	TODO: 实现迷宫算法
//

return flag;

}

// 判断链栈是否为空 bool IsEmpty(LinkStack *L) { if (L->count == 1) return true; return false; }

// 创建链栈 void CreateLink(LinkStack *L) { L->top = (LinkStackPtr)malloc(sizeof(struct StackNode)); if (!L->top) { exit(1); } L->top = NULL; L->count++; }

// 获取栈顶 LinkStackPtr GetTop(LinkStack *L) { return L->top; }

// 进栈 void Push(LinkStack *L, LinkStackPtr s) { s->next = L->top; L->top = s; L->count++; }

// 出栈 void Pop(LinkStack *L) { LinkStackPtr p; if (IsEmpty(L)) { return; } p = L->top; L->top = L->top->next; free(p); L->count--; }

// 记录探索路径 void RecordExplorationPath(LinkStackPtr m){ path[pathLength].x = m->position.x; path[pathLength].y = m->position.y; path[pathLength].seq = pathLength + 1; pathLength += 1; }

// 打印迷宫可通行的路径 void PrintPath(){ for (int i = 0; i < pathLength; i++) { printf("%d:(%d, %d)\n",path[i].seq, path[i].x, path[i].y); } return; } 下面是标准答案结果，右边是已删除的内容： 1 1:(2, 1) 2 2:(2, 2) 3 3:(2, 3) 4 4:(2, 4) 5 5:(2, 5) 6 6:(3, 5) 7 7:(3, 6) 8 8:(3, 7) 9 9:(2, 7) 10 10:(2, 8) 11 11:(1, 8) 12 12:(1, 9) 13 13:(4, 5) 14 14:(5, 5) 15 15:(6, 5) 16 16:(6, 6) 17 17:(6, 7) 18 18:(6, 8) 19 19:(6, 9) 请补全代码实现上述结果内容：首先，我们需要在maze.h头文件中定义一些结构体和函数的声明。

#ifndef MAZE_H
#define MAZE_H

#define row 8
#define col 11

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

typedef struct {
    int top;
    int right;
    int bottom;
    int left;
} Direction;

typedef struct StackNode {
    Position position;
    Direction direct;
    struct StackNode* next;
} * LinkStackPtr;

typedef struct {
    LinkStackPtr top;
    int count;
} LinkStack;

typedef struct {
    int x;
    int y;
    int seq;
} Path;

extern int map[row][col];
extern int enterx, entery;
extern int exitx, exity;
extern Path path[(row - 1) * (col - 1)];
extern int pathLength;

bool Panduan(int x, int y);
bool Maze(LinkStack* L);
bool IsEmpty(LinkStack* L);
void CreateLink(LinkStack* L);
LinkStackPtr GetTop(LinkStack* L);
void Push(LinkStack* L, LinkStackPtr s);
void Pop(LinkStack* L);
void RecordExplorationPath(LinkStackPtr m);
void PrintPath();

#endif

接下来，我们需要实现这些函数。

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

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;           // 出口坐标

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

bool Panduan(int x, int y) {
    if (map[x][y] == 0) {
        return true;
    }
    return false;
}

bool Maze(LinkStack* L) {
    bool flag = false;

    LinkStackPtr p;
    p = (LinkStackPtr)malloc(sizeof(struct StackNode));
    p->position.x = enterx;
    p->position.y = entery;
    p->direct.top = 1;
    p->direct.right = 0;
    p->direct.left = 0;
    p->direct.bottom = 0;
    map[p->position.x][p->position.y] = 2;

    Push(L, p);

    while (!IsEmpty(L)) {
        LinkStackPtr node = GetTop(L);
        int x = node->position.x;
        int y = node->position.y;

        if (x == exitx && y == exity) {
            flag = true;
            break;
        }

        Direction direct = node->direct;
        Pop(L);

        // 上
        if (direct.top == 1 && x - 1 >= 0 && Panduan(x - 1, y)) {
            LinkStackPtr newNode = (LinkStackPtr)malloc(sizeof(struct StackNode));
            newNode->position.x = x - 1;
            newNode->position.y = y;
            newNode->direct.top = 1;
            newNode->direct.right = 0;
            newNode->direct.left = 0;
            newNode->direct.bottom = 0;
            map[x - 1][y] = 2;
            Push(L, newNode);
            RecordExplorationPath(newNode);
            continue;
        }

        // 右
        if (direct.right == 1 && y + 1 < col && Panduan(x, y + 1)) {
            LinkStackPtr newNode = (LinkStackPtr)malloc(sizeof(struct StackNode));
            newNode->position.x = x;
            newNode->position.y = y + 1;
            newNode->direct.top = 0;
            newNode->direct.right = 1;
            newNode->direct.left = 0;
            newNode->direct.bottom = 0;
            map[x][y + 1] = 2;
            Push(L, newNode);
            RecordExplorationPath(newNode);
            continue;
        }

        // 下
        if (direct.bottom == 1 && x + 1 < row && Panduan(x + 1, y)) {
            LinkStackPtr newNode = (LinkStackPtr)malloc(sizeof(struct StackNode));
            newNode->position.x = x + 1;
            newNode->position.y = y;
            newNode->direct.top = 0;
            newNode->direct.right = 0;
            newNode->direct.left = 0;
            newNode->direct.bottom = 1;
            map[x + 1][y] = 2;
            Push(L, newNode);
            RecordExplorationPath(newNode);
            continue;
        }

        // 左
        if (direct.left == 1 && y - 1 >= 0 && Panduan(x, y - 1)) {
            LinkStackPtr newNode = (LinkStackPtr)malloc(sizeof(struct StackNode));
            newNode->position.x = x;
            newNode->position.y = y - 1;
            newNode->direct.top = 0;
            newNode->direct.right = 0;
            newNode->direct.left = 1;
            newNode->direct.bottom = 0;
            map[x][y - 1] = 2;
            Push(L, newNode);
            RecordExplorationPath(newNode);
            continue;
        }
    }

    return flag;
}

bool IsEmpty(LinkStack* L) {
    if (L->count == 0) return true;
    return false;
}

void CreateLink(LinkStack* L) {
    L->top = NULL;
    L->count = 0;
}

LinkStackPtr GetTop(LinkStack* L) {
    return L->top;
}

void Push(LinkStack* L, LinkStackPtr s) {
    s->next = L->top;
    L->top = s;
    L->count++;
}

void Pop(LinkStack* L) {
    LinkStackPtr p;
    if (IsEmpty(L)) {
        return;
    }
    p = L->top;
    L->top = L->top->next;
    free(p);
    L->count--;
}

void RecordExplorationPath(LinkStackPtr m) {
    path[pathLength].x = m->position.x;
    path[pathLength].y = m->position.y;
    path[pathLength].seq = pathLength + 1;
    pathLength += 1;
}

void PrintPath() {
    for (int i = 0; i < pathLength; i++) {
        printf("%d:(%d, %d)\n", path[i].seq, path[i].x, path[i].y);
    }
    return;
}

int main(int argc, char* argv[]) {
    LinkStack L;
    CreateLink(&L);

    bool flag = Maze(&L);

    if (flag == true) {
        PrintPath();
    } else {
        printf("Can not find path");
    }

    return 0;
}

这样就完成了迷宫的路径探索算法。运行程序会输出迷宫的可通行路径。如果找不到路径，将输出"Can not find path"。

C语言迷宫探索算法实现 - 寻找迷宫路径

原文地址: https://www.cveoy.top/t/topic/peM4 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录