迷宫问题？ - C语言论坛

得分:0

我的代码：可能丑陋了点，没办法，现在的水平就只有这样了。

/********************************************************
** Highlight software by yzfy(雨中飞燕) http:// *
*********************************************************/
#include<iostream>
#include<ctime>
using namespace std;
const int m=12,p=15;          //迷宫的行数和列数
struct offsets              //前进方向表的结构定义
{
    int a,b;              //a,b是x,y(SeekPath函数参数)方向的偏移
    char *dir;              //dir是方向
};

int Maze[m+2][p+2];       //迷宫定义
int mark[m+2][p+2];      //访问标记数组
//各个方向的偏移表
offsets move[8]={{-1,0,"N"},{-1,1,"NE"},{0,1,"E"},{1,1,"SE"},
    {1,0,"S"},{1,-1,"SW"},{0,-1,"W"},{-1,-1,"NW"}};
int main()
{
    int SeekPath(int,int);
    int i,j;
    srand(unsigned(time(NULL)));
    for(i=0;i<m+2;i++)               //用随机数产生迷宫
    {
        for(j=0;j<=p+1;j++)
            Maze[i][j]=rand()%2;
    }
    //设定行边界
    for(j=0;j<=p+1;j++)
    {
        Maze[0][j]=Maze[m+1][j]=1;
    }
    //设定列边界
    for(i=0;i<=m+1;i++)
    {
        Maze[i][0]=Maze[i][p+1]=1;
    }
    for(i=0;i<m+2;i++)                 //访问标记数组初始为零
        for(j=0;j<p+2;j++)
            mark[i][j]=0;
    cout<<"The maze is:"<<endl;         //输出刚才产生的迷宫
    for(i=0;i<m+2;i++)
    {
        for(j=0;j<p+2;j++)
            cout<<Maze[i][j];
        cout<<endl;
    }
    mark[1][1]=1;                    //从入口[1][1]开始

    if(SeekPath(1,1))                //调用求解迷宫的递归算法
        cout<<"("<<1<<","<<1<<"(,"<<"Direction"<<"E"<<endl;
    system("pause");
    return 0;
}
int SeekPath(int x,int y)
{
    //从迷宫某一位置开始，寻找通向出口[M][P]的一条路径。
    //如果找到，返回1，否刚返回0；
    //试探的出发点为[1][1].
    int i,g=0,h=0;                    //用G，H记录位置信息，D记方向
    char *d=NULL;
    if(x==m&&y==p)
        return 1;                     //到达出口，返回1;
    for(i=0;i<8;i++)
    {
        g=x+move[i].a;
        h=y+move[i].b;
        d=move[i].dir;              //找下一位置和方向(a,b,dir)
        if(Maze[g][h]==0 && mark[g][h]==0)
        {
            mark[g][h]=1;
            if(SeekPath(g,h))              //从此位置递归试探
            {
                cout<<"("<<g<<","<<h<<"),"<<"Direction  "<<d<<endl;
                return 1;                //试探成功，逆向输出路径坐标
            }
        }
    }
    if(x==1&&y==1)
        cout<<"no path in Maze"<<endl;
    return 0;
}

i like linux...

第 22 楼

得分:0

呵呵，赞一个

[color=white]

第 23 楼

得分:0

非递归解法已出来，由于刚才递归解法中遇到的问题，在飞燕姐的帮肋下，已解决，所以写这个这少了很多麻烦，注意了几个问题，所以只要算法正确，就能写出来了。程序中还有不足之处，以后再优化了，一高兴就先把代码发上来了，呵呵。再次感谢飞燕姐。
这次输出的只是出口，是我自已设定的。为（12，15）。试了几十次，五次成功找到出口。代码如下：

/********************************************************
** Highlight software by yzfy(雨中飞燕) http:// *
*********************************************************/
#include<iostream>
#include<ctime>
#include<stack>
using namespace std;
//前进方向表的结构定义
struct offsets
{
    int a,b;          //a,b是方向的偏移
    char *dir;        //dir是方向
};
//栈中的三元组结构
struct items
{
    int x,y,dir;             //位置和前进方向序号
};
offsets move[8]={{-1,0,"N"},{-1,1,"NE"},{0,1,"E"},{1,1,"SE"},
    {1,0,"S"},{1,-1,"SW"},{0,-1,"W"},{-1,-1,"NW"}};
const int m=12,p=15;
int mark[m+2][p+2];
int Maze[m+2][p+2];
//输出迷宫路径操作的实现
    ostream& operator<<(ostream& os,items& item)
{
    return os<<item.x<<" ,"<<item.y<<" ,"<<item.dir<<endl;
}

int main()
{
    void path(int m,int p);              //寻找出口函数
    srand(unsigned(time(NULL)));
    int i,j;
    //用随机数产生迷宫
    for(i=0;i<m+2;i++)
        for(j=0;j<p+2;j++)
            Maze[i][j]=rand()%2;
    //初始化标记数组
    for(i=0;i<m+2;i++)
        for(j=0;j<p+2;j++)
            mark[i][j]=0;
    //设定行边界
    for(j=0;j<p+2;j++)
        Maze[0][j]=Maze[m+1][j]=1;
    //设定列边界
    for(i=0;i<m+2;i++)
        Maze[i][0]=Maze[i][p+1]=1;
    //输出迷宫
    for(i=0;i<m+2;i++)
    {
        for(j=0;j<p+2;j++)
            cout<<Maze[i][j];
        cout<<endl;
    }
    path(m,p);
    system("pause");
    return 0;
}
void path(int m,int p)
{
    int i,j,d,g,h;
    mark[1][0]=1;           //设置入口
    stack<items> st;
    items tmp;
    tmp.x=1;tmp.y=0;tmp.dir=2;
    st.push(tmp);
    //栈不空，持续走下去
    while(st.empty()==false)
    {
        st.pop();              //退栈
        i=tmp.x;j=tmp.y;d=tmp.dir;         //d为前进方向表下标
        while(d<8)
        {
            g=i+move[d].a;h=j+move[d].b; //找下一个位置
            if(g==m&&h==p)                //找到出口
            {
                //cout<<st;
                cout<<m<<"  "<<p<<endl;   //输出出口位置
                return ;
            }
            if(Maze[g][h]==0&&mark[g][h]==0)    //新的路径可通
            {
                mark[g][h]=1;                  //标记为已访问过
                tmp.x=i;
                tmp.y=j;
                tmp.dir=d;
                st.push(tmp);               //进栈
                i=g;j=h;d=0;   //移动到（G，H），在各方向试探
            }
            else
                d++;           //试探下一个方向
        }
    }
    cout<<"no path in maze!"<<endl;
}

[[it] 本帖最后由 zjl138 于 2008-5-6 16:59 编辑 [/it]]

i like linux...

第 24 楼

得分:0

我也写个简单的..固定出入口的非递归算法
#include <stdio.h>
#include <stdlib.h>
#define M    5
#define N    5
void serch_road(int map[][N],int m,int n)
{
    int is[8]={-1,-1,-1, 0,0, 1,1,1};
    int js[8]={-1, 0, 1,-1,1,-1,0,1};
    int stack[3*M*N],*top;
    int i,j,v,g,h,jt;
    top=stack;
    i=j=v=0;
    if(map[0][0]!=0)
    {
        map[0][0]=4;
        printf("1.no path!\n");
        return;
    }
    while(top!=stack||v!=7)
    {
        g=i+is[v];
        h=j+js[v];

        jt=0;
        if(g>-1&&g<m&&h>-1&&h<n)
        {   //printf("%d %d %d\n",g,h,map[g][h]);
            if(g==m-1&&h==n-1&&map[m-1][n-1]==0)
            {
                map[i][j]=8;
                map[g][h]=8;
                return;
            }
            if(map[g][h]==0)
            {
                map[g][h]=4;
                map[i][j]=8;
                top+=3;
                top[0]=i;
                top[1]=j;
                top[2]=v;
                i=g;
                j=h;
                v=0;
                jt=1;
            }
        }
        if(jt==0)
        {
            if(v<7) v++;
            else
            {
                while(top!=stack&&top[2]==7)
                {    map[top[0]][top[1]]=4;
                    top-=3;
                }

                if(top!=stack)
                {
                i=top[0];
                j=top[1];
                v=top[2];
                map[i][j]=4;
                top-=3;
                }
            }
        }
    }
    printf("2.no path! \n");
    return;
}
int main()
{
       int i,j;
    int map[M][N]={    {0,1,1,1,1},
                    {0,1,1,0,1},
                    {0,0,0,1,1},
                    {0,1,0,0,1},
                    {0,0,1,1,0}};

    serch_road(map,M,N);
    for(i=0;i<M;i++)
    {
        for(j=0;j<N;j++)
            printf("%d ",map[i][j]);
        printf("\n");
    }
    getchar();
    return 0;
}

学习需要安静。。海盗要重新来过。。