迷宫问题 - 编程论坛

#2

鬼鬼千年2010-05-28 12:38

这个是我以前写的，自己看着改吧

#include<stdio.h>

int maze[10][10] = {
        {1,1,1,1,1,1,1,1,1,1},
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,1,0,0,0,1,0,1},
        {1,0,0,0,0,1,1,0,0,1},
        {1,0,1,1,1,0,0,0,0,1},
        {1,0,0,0,1,0,0,0,0,1},
        {1,0,1,0,0,0,1,0,0,1},
        {1,0,1,1,1,0,1,1,0,1},
        {1,1,1,0,0,0,0,0,0,1},
        {1,1,1,1,1,1,1,1,1,1}};/*初始化迷宫*/
int mark[10][10] = {0};/*初始化标志位,0代表没走过,1代表走过*/

/*方向*/
typedef struct{
    short int vert;
    short int horiz;
}offsets;

offsets move[4] = {{0,1},{1,0},{0,-1},{-1,0}};/*北,东,南,西*/

/*迷宫类型*/
typedef struct element{
    short int row;
    short int col;
    short int dir;
}element;

element stack[100];

void path(void);
  element del(int* top);
void add(int* top,element item);

element del(int* top)/*出栈,top指向栈顶元素*/
{
    if(*top == -1)
    {
        printf("stack is empty!\n");
    }
    return stack[(*top)--];
}

void add(int* top,element item)/*入栈*/
{
    if(*top >= 100)
    {
        printf("stack is full!\n");
        return;
    }
    stack[++*top] = item;
}

void path(void)/*迷宫函数*/
{
    element position;
    int i,row,col,next_row,next_col,dir,top;
    int found = 0;
    mark[1][8] = 1,top = 0;/*初始化标志数组元素以及栈*/
    stack[0].row = 1,stack[0].col = 8,stack[0].dir = 0;
    while(top > -1 && !found)
    {
          position= del(&top);  /*将栈顶元素取出,*/
        row = position.row;            /*利用中间变量row,col,dir等候判断*/
        col = position.col;
        dir = position.dir;
        while(dir < 4 && !found)
        {
            next_row = row + move[dir].vert;
            next_col = col + move[dir].horiz;
            if(row == 7 && col == 1)
                found = 1;
            else if(!maze[next_row][next_col] && !mark[next_row][next_col])/*判断下一步可走并且没走过,则入栈*/
                    {
                        mark[next_row][next_col] = 1;
                        position.row = row;
                        position.col = col;
                        position.dir = ++dir;
                        add(&top,position);/*合理则入栈*/
                        row = next_row;/*继续向下走*/
                        col = next_col;dir = 0;
                    }
                    else
                        dir++;/*dir<4时,改变方向*/

        }
        if(found)/*判断是否有出口*/
        {
            printf("the path is:\n");
            printf("row col\n");
            for(i = 0;i <= top;++i)
                printf("(%2d,%5d)",stack[i].row,stack[i].col);
                printf("(%2d,%5d)\n",7,1);


        }


    }
    if(found==0)
        printf("没有路径\n");
}

int main(void)
{
    path();

return 0;
}

#3

xichong2010-05-28 15:31

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 10000
#define STACKINCREMENT 100
#define M 10
#define N 10
int flag=0;
typedef struct//坐标位置
{
    int x;
    int y;
}PosType;
typedef struct//栈中元素结构体
{
    int ord;//序号
    PosType seat;//坐标位置
    int di;//通道方向(1东2南3西4北)
}SElemType;
typedef struct//栈
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;
////////////////////////////////////////栈操作
void initialStack(SqStack *s)
{
    s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!s->base) exit(0);
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *s,SElemType e)
{
    if(s->top-s->base>=s->stacksize)
    {
        s->base=(SElemType *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));
        if(!s->base) exit(0);
        s->top=s->base+s->stacksize;
        s->stacksize+=STACKINCREMENT;
    }
    (*(s->top)).ord=e.ord;
    (*(s->top)).seat.x=e.seat.x;
    (*(s->top)).seat.y=e.seat.y;
    (*(s->top)).di=e.di;
    s->top++;
}
void Pop(SqStack *s,SElemType *e)
{
    if(s->top==s->base) exit(0);
    (s->top)--;
    e->ord=(*(s->top)).ord;
    e->seat.x=(*(s->top)).seat.x;
    e->seat.y=(*(s->top)).seat.y;
    e->di=(*(s->top)).di;
}
int StackEmpty(SqStack *s)
{
    if(s->top==s->base) return(1);
    else return(0);
}
void ClearStack(SqStack *s)
{
    s->top=s->base;
    s->stacksize=0;
}
//////////////////////////////////////////初始化迷宫
void initialarray(int (*p)[N])
{
    int i,j;
    int maze[M][N]={1,1,1,1,1,1,1,1,1,1,
                    1,0,0,1,0,0,0,1,0,1,
                    1,0,0,0,0,1,0,1,0,1,
                    1,0,0,1,1,0,0,0,0,1,
                    1,1,1,1,1,0,0,1,0,1,
                    1,0,0,0,1,0,0,0,0,1,
                    1,0,1,0,0,1,1,0,0,1,
                    1,0,1,1,1,0,1,1,0,1,
                    1,1,0,0,0,0,0,0,0,1,
                    1,1,1,1,1,1,1,1,1,1};/***/
    printf("打印迷宫:\n");
    for(i=0;i<M;i++)
    {
        for(j=0;j<N;j++)
        {
            printf("%d",maze[i][j]);
            *(*(p+i)+j)=maze[i][j];/***/
        }
        printf("\n");
    }
}
///////////
void NextPos(PosType *p,int d)//确定下一个位置的坐标
{
    switch(d)
    {
    case 1:p->y++;break;
    case 2:p->x++;break;
    case 3:p->y--;break;
    case 4:p->x--;break;
    }    /////////////////////////(1东2南3西4北)改变坐标
}
void MazePath(int (*maze)[N])//核心函数//---int (*maze)[N]
{
    int curstep;
    int mark[M][N]={0};
    SqStack s;
    PosType curpos;
    SElemType e;//栈中元素结构体 1.序号;2.坐标位置;3.通道方向
    initialStack(&s);
    curpos.x=1;
    curpos.y=1;
    curstep=1;
    do
    {
        if((!maze[curpos.x][curpos.y])&&(!mark[curpos.x][curpos.y]))//*******
        {
            mark[curpos.x][curpos.y]=1;
            e.ord=curstep;//**e=(curstep,curpos,1)
            e.seat.x=curpos.x;
            e.seat.y=curpos.y;
            e.di=1;//***
            Push(&s,e);
            if((curpos.x==M-2)&&(curpos.y==N-2))
            {

                flag=1;
                printf("走出迷宫的一条坐标路径为:\n[终点]");
                while(!StackEmpty(&s))
                {
                    Pop(&s,&e);
                    printf("<--(%d,%d)",e.seat.x,e.seat.y);
                }
                printf("<--[起点]");
                printf("\n");
                ClearStack(&s);
            }
                NextPos(&curpos,1);//curpos=NextPos(curpos,1)
                curstep++;
        }
            else
            {
                if(!StackEmpty(&s))
                    Pop(&s,&e);
                while(e.di==4&&!StackEmpty(&s))
                {
                    mark[e.seat.x][e.seat.y]=1;
                    Pop(&s,&e);
                }
                if(e.di<4)
                {
                    e.di++;
                    Push(&s,e);
                    curpos.x=e.seat.x;//**curpos=NextPos(e.seat,e,di)
                    curpos.y=e.seat.y;
                    NextPos(&curpos,e.di);///**
                }
            }
    }while(!StackEmpty(&s));
}
void main()
{
    int array[M][N];
    initialarray(array);
    MazePath(array);
    if(flag==0)
        printf("该迷宫不能走出去!\n");
}

#4

qq88011032010-05-28 18:44

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 10000
#define STACKINCREMENT 100
#define M 10
#define N 10
int flag=0;
typedef struct//坐标位置
{
    int x;
    int y;
}PosType;
typedef struct//栈中元素结构体
{
    int ord;//序号
    PosType seat;//坐标位置
    int di;//通道方向(1东2南3西4北)
}SElemType;
typedef struct//栈
{
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;
////////////////////////////////////////栈操作
void initialStack(SqStack *s)
{
    s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!s->base) exit(0);
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}
void Push(SqStack *s,SElemType e)
{
    if(s->top-s->base>=s->stacksize)
    {
        s->base=(SElemType *)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));
        if(!s->base) exit(0);
        s->top=s->base+s->stacksize;
        s->stacksize+=STACKINCREMENT;
    }
    (*(s->top)).ord=e.ord;
    (*(s->top)).seat.x=e.seat.x;
    (*(s->top)).seat.y=e.seat.y;
    (*(s->top)).di=e.di;
    s->top++;
}
void Pop(SqStack *s,SElemType *e)
{
    if(s->top==s->base) exit(0);
    (s->top)--;
    e->ord=(*(s->top)).ord;
    e->seat.x=(*(s->top)).seat.x;
    e->seat.y=(*(s->top)).seat.y;
    e->di=(*(s->top)).di;
}
int StackEmpty(SqStack *s)
{
    if(s->top==s->base) return(1);
    else return(0);
}
void ClearStack(SqStack *s)
{
    s->top=s->base;
    s->stacksize=0;
}
//////////////////////////////////////////初始化迷宫
void initialarray(int (*p)[N])
{
    int i,j;
    int maze[M][N]={1,1,1,1,1,1,1,1,1,1,
                    1,0,0,1,0,0,0,1,0,1,
                    1,0,0,0,0,1,0,1,0,1,
                    1,0,0,1,1,0,0,0,0,1,
                    1,1,1,1,1,0,0,1,0,1,
                    1,0,0,0,1,0,0,0,0,1,
                    1,0,1,0,0,1,1,0,0,1,
                    1,0,1,1,1,0,1,1,0,1,
                    1,1,0,0,0,0,0,0,0,1,
                    1,1,1,1,1,1,1,1,1,1};/***/
    printf("打印迷宫:\n");
    for(i=0;i<M;i++)
    {
        for(j=0;j<N;j++)
        {
            printf("%d",maze[i][j]);
            *(*(p+i)+j)=maze[i][j];/***/
        }
        printf("\n");
    }
}
///////////
void NextPos(PosType *p,int d)//确定下一个位置的坐标
{
    switch(d)
    {
    case 1:p->y++;break;
    case 2:p->x++;break;
    case 3:p->y--;break;
    case 4:p->x--;break;
    }    /////////////////////////(1东2南3西4北)改变坐标
}
void MazePath(int (*maze)[N])//核心函数//---int (*maze)[N]
{
    int curstep;
    int mark[M][N]={0};
    SqStack s;
    PosType curpos;
    SElemType e;//栈中元素结构体 1.序号;2.坐标位置;3.通道方向
    initialStack(&s);
    curpos.x=1;
    curpos.y=1;
    curstep=1;
    do
    {
        if((!maze[curpos.x][curpos.y])&&(!mark[curpos.x][curpos.y]))//*******
        {
            mark[curpos.x][curpos.y]=1;
            e.ord=curstep;//**e=(curstep,curpos,1)
            e.seat.x=curpos.x;
            e.seat.y=curpos.y;
            e.di=1;//***
            Push(&s,e);
            if((curpos.x==M-2)&&(curpos.y==N-2))
            {

                flag=1;
                printf("走出迷宫的一条坐标路径为:\n[终点]");
                while(!StackEmpty(&s))
                {
                    Pop(&s,&e);
                    printf("<--(%d,%d)",e.seat.x,e.seat.y);
                }
                printf("<--[起点]");
                printf("\n");
                ClearStack(&s);
            }
                NextPos(&curpos,1);//curpos=NextPos(curpos,1)
                curstep++;
        }
            else
            {
                if(!StackEmpty(&s))
                    Pop(&s,&e);
                while(e.di==4&&!StackEmpty(&s))
                {
                    mark[e.seat.x][e.seat.y]=1;
                    Pop(&s,&e);
                }
                if(e.di<4)
                {
                    e.di++;
                    Push(&s,e);
                    curpos.x=e.seat.x;//**curpos=NextPos(e.seat,e,di)
                    curpos.y=e.seat.y;
                    NextPos(&curpos,e.di);///**
                }
            }
    }while(!StackEmpty(&s));
}
void main()
{
    int array[M][N];
    initialarray(array);
    MazePath(array);
    if(flag==0)
        printf("该迷宫不能走出去!\n");
}

#5

linshijin2010-12-08 17:14

//*laoshu.h 系统主文件
//迷宫用字符型二维数组存储
//迷宫随机生成
//其中"*"表示墙
//" "表示路
//"=="表示走过的无用的路
//"+"表示走过的有用的路
//"^"表示当前老鼠所在的位置
//TIMEMAX可以设定执行速度
#include<iostream.h>
#include<stdlib.h>
#include<process.h>
#include<time.h>
#include<malloc.h>
#define TIMEMAX 6000
#define OK 0
#define ERROR -1
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4
char arr[18][70];

typedef struct SNode
{
    int data;
    struct SNode *next;
}SNode;

class Stack
{
    private:
    SNode *top;
    public:
    Stack();//构造函数，与类同名
    int totallength;//记载栈操作次数
    int length;//记录栈深度
    int Push(int e);//元素e入栈操作
    int Pop();//出栈操作，返回栈顶元素
    int IsEmpty();//判断栈是否为空
};

Stack::Stack()//构造函数，与类同名
{
    top=NULL;
    length=0;
    totallength=0;
}
int Stack::Push(int e)//元素e入栈操作
{
    SNode *p;
    p=(SNode *)malloc(sizeof(SNode));
    if(!p)
    return ERROR;
    p->data=e;
    p->next=top;
    top=p;
    length++;
    totallength++;
    return OK;
}
int Stack::Pop()//出栈操作，返回栈顶元素
{
    int e;
    SNode *p;
    if(top==NULL)
    return ERROR;
    e=top->data;
    p=top;
    top=p->next;
    length--;
    totallength++;
    delete p;
    return e;
}
int Stack::IsEmpty()//判断栈是否为空
{
    if(top==NULL)
    return OK;
    return ERROR;
}

//显示迷宫函数
void ShowMaze()
{
    int i,j;
    system("cls.exe");//清屏
    for(i=0;i<18;i++)
    {
        //利用二维数组arr绘制老鼠及迷宫图
        for(j=0;j<70;j++)
        cout<<arr[i][j];
        cout<<"\n";
    }
    cout<<"*表示墙 ^表示老鼠空格表示路 +表示有用的路 =表示无用的路"<<endl;
}

//迷宫初始化函数
void InitMaze()
{
    int n,i,j;
    for(i=0;i<18;i++)
    for(j=0;j<70;j++)
    arr[i][j]='*';//先把迷宫的所有位置都画上'*'表示墙
    srand((unsigned)time(NULL));//随机函数做种
    for(i=1;i<17;i++)
    for(j=1;j<69;j++)
    {
        n=rand()%25;//利用随机函数随机生成n值
        if(n<17)
        arr[i][j]=' ';//随机设置通道
    }
    arr[1][0]=' ';
    arr[1][1]=' ';
    arr[1][2]=' ';
    arr[1][3]=' ';
    arr[16][66]=' ';
    arr[16][67]=' ';
    arr[16][68]=' ';
    arr[16][69]=' ';
}//给迷宫绘制出口

//主函数
void main()
{
    int i,j,path,speed=0;
    long timei,timej;
    Stack s;//定义一个用于存储老鼠走过路线的栈
    InitMaze();//随机生成迷宫

    i=1;
    j=0;
    arr[i][j]='^';//初始化老鼠位置
    ShowMaze();//显示迷宫
    cout<<"选择速度：1 快速 2较慢"<<endl;
    while(speed!=1&&speed!=2)
    cin>>speed;
    while(i>=0&&i<18&&j>=0&&j<70)//开始进迷宫
    {
        ShowMaze();
        if(speed==2)
        for(timei=0;timei<TIMEMAX;timei++)
        for(timej=0;timej<TIMEMAX;timej++)
        if(i==16&&j==69)
        {
            cout<<"老鼠逃出来了！";
            cout<<"老鼠总共跑了:"<<s.totallength<<"步 ";
            cout<<"有用的步数为:"<<s.length <<endl;
            exit(1);
        };
        if(arr[i][j+1]==' ')//向右一步
        {
            arr[i][j]='+';
            j=j+1;
            arr[i][j]='^';
            s.Push(RIGHT);
            continue;
        };
        if(arr[i+1][j]==' ')//向下走一步
        {
            arr[i][j]='+';
            i=i+1;
            arr[i][j]='^';
            s.Push(DOWN);
            continue;
        };
        if(arr[i-1][j]==' ')//向上走一步
        {
            arr[i][j]='+';
            i=i-1;
            arr[i][j]='^';
            s.Push(UP);
            continue;
        };
        if(arr[i][j-1]==' ')//向左走一步
        {
            arr[i][j]='+';
            j=j-1;
            arr[i][j]='^';
            s.Push(LEFT);
            continue;
        };
        //上下左右都无路可走
        if(s.IsEmpty()==OK)
        {
            cout<<"可怜的老鼠，迷宫没有出路!\n"<<endl;
            exit(1);
        };
        path=s.Pop();
        switch(path)
        {
            case LEFT:
            arr[i][j]='=';
            j=j+1;
            arr[i][j]='^';
            break;
            case UP:
            arr[i][j]='=';
            i=i+1;
            arr[i][j]='^';
            break;
            case DOWN:
            arr[i][j]='=';
            i=i-1;
            arr[i][j]='^';
            break;
            case RIGHT:
            arr[i][j]='=';
            j=j-1;
            arr[i][j]='^';
            break;
        }
    };
}

#6

许玉飞嵩2014-06-06 16:01

回复 5 楼 linshijin

哥哥厉害啊，小弟有一事相求。。。我们老师让做一个课程设计，用栈实现小鼠走迷宫，我不用栈已经写出来了，可老师还是要求用栈，求帮忙啊
要求如下
　　　3、迷宫问题
   以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
　　基本要求：
　　（1）实现一个栈类型，然后编写一个求解迷宫的程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。
（2）求得迷宫中所有可能的通路；
　　（3）以方阵形式输出迷宫及其通路。（选做）
　　测试数据：
　　　迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口。
                 1     2      3     4     5     6      7     8
0    0    1    0    0    0    1    0
0    0    1    0    0    0    1    0
0    0    0    0    1    1    0    1
0    1    1    1    0    0    1    0
0    0    0    1    0    0    0    0
0    1    0    0    0    1    0    1
0    1    1    1    1    0    0    1
1    1    0    0    0    1    0    1
1    1    0    0    0    0    0    0
　　实现提示：
　　　计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
　　　可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。