maze1.txt

一个maze迷宫程序。内附源码注释。里面的算法便于初学者学习参考。

　第1楼  

很久以前编的迷宫＇E是入口，Ｓ是出口＇
#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
#define N 8

/////////////////////算法一:
typedef struct stack{
    int I;
    int J;
    int step;//步数
    stack *next;
}STACK;

STACK *top;

STACK* InitStack()
{
    top=(STACK *)malloc(sizeof(STACK));
    top->next=NULL;
    top->step=0;
    return top;
}

void push(int i,int j)
{
    STACK *p;
    p=(STACK *)malloc(sizeof(STACK));
    p->I=i;
    p->J=j;
    p->next=top->next;
    top->next=p;
    top->step++;
}

int pop(int &i,int &j)
{
    STACK *p;
    if(top->next){
        p=top->next;
        top->next=p->next;
    }
    else if(top->next==NULL)
        return 0;
    i=p->I;
    j=p->J;
    top->step--;
    return 1;
}

int ok(char a[][N],int i,int j)
{
    while((i<N&&i>=0)&&(j<N&&j>=0)){
        if(a[i][j]=='S'){//找到出口
            break;
        }
        if(a[i-1][j]!='X'&&a[i-1][j]!='Y'){    //上边不是墙且不是死路，并且没有走过则压栈                                        
            a[i][j]='X';//经过该点则标记，否则在N000 处会造成原路返回结果
            push(i,j);    //                         000S    
            i=i-1;
            continue;
        }
        if(a[i+1][j]!='X'&&a[i+1][j]!='Y'){//下
            a[i][j]='X';
            push(i,j);    
            i=i+1;
            continue;
        }
        
        if(a[i][j-1]!='X'&&a[i][j-1]!='Y'){//左
            a[i][j]='X';
            push(i,j);    
            j=j-1;
            continue;
        }
        if(a[i][j+1]!='X'&&a[i][j+1]!='Y'){//右
            a[i][j]='X';
            push(i,j);    
            j=j+1;    
            continue;
        }
        //四个方向都不通
        a[i][j]='Y';//Y表示此路已经走过但是不通，否则会在该处造成无限循环
        int s;
        s=pop(i,j);
        if(!s)
            return 0;    
    }
    return 1;
}

int main(int argc, char* argv[])
{
    char a[N][N]={  'X','X','X','X','X','X','X','X',\
                    'X','E','0','0','X','S','X','X',\
                    'X','X','0','X','0','X','X','X',\
                    'X','0','0','0','0','X','0','X',\
                    'X','X','X','X','0','0','0','X',\
                    'X','0','0','0','0','X','X','X',\
                    'X','X','X','X','0','X','X','X',\
                    'X','X','X','X','X','X','X','X',};

    int i,j,i0,j0;
    
    InitStack();
    for(i=0;i<N;i++){
        for(j=0;j<N;j++)
            if(a[i][j]=='E'){
                i0=i;
                j0=j;
            }
    }
    int s;
    s=ok(a,i0,j0);
    if(!s){
        printf("迷宫走不通");
        exit(0);
    }
    printf("%d步可以走出迷宫",top->step);
    while(top->next){
        pop(i,j);
        a[i][j]='*';
    }
    
    for(i=0;i<N;i++){
        printf("\n");
        for(j=0;j<N;j++){
            if(a[i][j]=='Y')//将Y还原
                a[i][j]='0';
            printf("%c",a[i][j]);
        }
    }
    return 0;
}