Question

数据结构迷宫问题 C++算法

C++编译，栈结构
要求用户输入迷宫的大小m行和n列，两者为整数2.由输入的m和n，随机产生0或1，建立迷宫3.输出模拟的迷宫，若存在最短路径，则由出口回溯到入口打印这一条路径，如下所示：（m，n），...,(i,j),...,(1,1)如无通道，则输出：没有通路
求大神给个代码吧，最好是源文件，急用所以来求C++大神

Answer 1

/*百度作个东西能用点心么 代码区的代码丑爆了
 *程序的框架:宏定义，函数声明，main函数，函数实现
 * =========================================================
 *       Filename:  maze.c
 *    Description:  基于栈寻找迷宫路径
 *
 * =========================================================
 */
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define ROW 10 /*迷宫大小*/
#define COL 10
#define STACKSIZE 100  /*栈大小*/
#define ISEND(n) ((n).p.x==ROW-1 &&(n).p.y==COL-1)/*判断该位置是否为出口*/
#define ISVALID(n) ((n).visit== NO &&((n).path== YES))/*判断该位置是否可走*/
#define ISEMPTY(s) (s.top==0)
enum Bool{
    NO,
    YES
};
/*---------------------------------------------------
 *  棋盘由R*C 个节点构成，每个节点包含的信息由:
 *  节点位置(x,y) , 是否是死路(yes/no) , 是否被访问过(yes/no)
 *---------------------------------------------------*/
typedef struct point Point;
typedef struct node Node;
typedef struct maze Maze;
struct point{
    int x,y;
};
struct node{
    Point p;
    int path;
    int visit;
};
struct maze{
    Node ma[ROW][COL];
};
/*---------------------------------------------------
 *  1.初始化迷宫,每个节点有4/5的概率可走
 *  2.输出迷宫的构造
 *---------------------------------------------------*/
void Initmaze(Maze *m);
void printmaze(Maze m);
/*---------------------------------------------------
 *  存储访问过程的栈及相应操作
 *---------------------------------------------------*/
typedef struct stack Stack;
struct stack{
    Node *no[STACKSIZE];
    int top;
};
Stack s;
void push(Node * n);
Node* pop();
void print(Stack s);


/*---------------------------------------------------
 *  find path based on stack  这个是关键函数，基于回溯思想
 *---------------------------------------------------*/
int findpath(Maze *m,Node *n);

int main(){
    Maze m;
    Initmaze(&m);
    printmaze(m);
    Node *n=m.ma[0];
    if(findpath(&m,n))
        print(s);
}

void Initmaze(Maze *m){
    int i,j;
    srand(time(NULL)); /* initialize random seed */
    for(i=0;i<ROW;i++)
        for(j=0;j<COL;j++){
            m->ma[i][j].visit=NO;
            m->ma[i][j].p.x=i;
            m->ma[i][j].p.y=j;
            m->ma[i][j].path=((i==0 && j==0) || (i==ROW-1 && j==COL-1) || rand()%ROW < 4*ROW/5)?YES:NO;
        }
}

int findpath(Maze *m,Node *n){
    while(!ISEND(*n)){
        if(n->visit==NO){
            n->visit=YES;
            push(n);
        }
        int current_x=n->p.x;
        int current_y=n->p.y;
        if(current_y+1<COL && ISVALID(m->ma[current_x][current_y+1])) /* rigth valid */
            n=m->ma[current_x]+current_y+1;
        else if(current_x+1<ROW && ISVALID(m->ma[current_x+1][current_y])) /* down valid */
            n=m->ma[current_x+1]+current_y;
        else if(current_x-1>=0 && ISVALID(m->ma[current_x-1][current_y])) /* up valid */
            n=m->ma[current_x-1]+current_y;
        else if(current_y-1>=0 && ISVALID(m->ma[current_x][current_y-1])) /* left valid */
            n=m->ma[current_x]+current_y-1;
        else{
            pop(); /* current n is not valid */
            if(!ISEMPTY(s)) /* n point to pre */
                n=s.no[s.top-1];
            else{
                printf("stack empty.\n");
                n=NULL;
                break;
            }
        }
    }
    if(n==NULL)
        return 0;
    else{
        push(n);
        return 1;
    }

}

void push(Node * n){
    s.no[s.top++]=n;
}
Node * pop(){
    if(s.top!=0)
        return s.no[--s.top];
    else{
        printf("%s","stack empty\n");
        return NULL;
    }
}

void print(Stack s){
    int iter;
    for(iter=0;iter<s.top;iter++)
        printf("%d %d\n",s.no[iter]->p.x,s.no[iter]->p.y);
}
void printmaze(Maze m){
    int i,j;
    for(i=0;i<ROW;i++)
        for(j=0;j<COL;j++)
            printf("%d%s",m.ma[i][j].path,(j==COL-1)?"\n":" ");
}

给C行么，改改就是了。

output:如果无路径

如果有路径.

追问

“用户输入迷宫的大小m行和n列，由输入的m和n，随机产生0或1，建立迷宫”，这个功能可以实现吗？

追答

这个程式里迷宫的大小在宏里定义了。根据用户的输入来构造迷宫，需要重写构建迷宫的函数，用动态内存分配就ok啦，在C里就是malloc那一套。

追问

我手比较残...时间也不多了，不然也不会来要了，不过写这么多辛苦你了，要是大神您有空帮我改成我要求里面的，我直接就采纳了，感激不尽

追答

//把这两个注释掉
//#define ROW 5
//#define COL 5
//声明全局变量 ROW ,COL
int ROW,COL;

//修改maze的结构体
struct maze{
//    Node ma[ROW][COL];
    Node **ma;
};

//在main函数添加
printf("input row and col:\n");
    scanf("%d%d",&ROW,&COL);

//在Initmaze函数srand(time(NULL)); 后添加
m->ma=malloc(ROW*sizeof(int *));
for(i=0;i<ROW;i++)
    m->ma[i]=malloc(COL*sizeof(int));