| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1224 人关注过本帖
标题:作为新手琢磨了一天,终于想出走迷宫的暴力算法。
取消只看楼主 加入收藏
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
 问题点数:0 回复次数:2 
作为新手琢磨了一天,终于想出走迷宫的暴力算法。
//写完以后走是走出来了,但这个代码实在是。。。。
//怎么才能写出飞燕那样优雅的代码阿?大哥大姐们教教我啊。
#include <iostream>
#include <stdio.h>

using namespace std;

#define N 9
////////////////////////////////////////////////////////////////////////
// CStack can noly push 100 ints as max
//
class CStack // int stored only
{
    private:
    int nData[101]; // Storage
    int nTop; // Pointer to top Storage
   
    public:
    CStack(); // constructor
    int Push  (int );
    int Pop   ();
    int GetTop();
    void Show ();// only for testing not use in prog.
};   

CStack::CStack()
{
    for (int i=0;i<101;i++) nData[i]=0;
    nTop=0;
}
   
int CStack::Push(int data)
{
    if (nTop==100) return 1;
    nData[nTop++]=data;
    return 0;
}

int CStack::Pop()
{
    if (nTop==0) return 1;
    nTop--;
    return 0;
}   

void CStack::Show() // Only for Testing
{
    for (int i=0;i<=nTop;i++) printf("%d ",nData[i]+1);
    printf ("\n");
}

int CStack::GetTop()
{
    if (nTop==0) return nData[nTop];
    return nData[nTop-1];
}  


//////////////////////////////////////////////////////////////////
// Global variables
int nMap[N][N]={{1, 1, 1, 1, 1, 1, 1, 1, 1}, // 1: wall
                {1, 0, 0, 0, 1, 1, 1, 0, 1}, // 0: walk path
                {1,-2, 1, 0, 0, 0, 0 ,0 ,1}, // -1: start point
                {1, 1, 1, 0, 1, 1, 1, 1, 1}, // -2: end point
                {1, 0, 1, 0, 0, 0, 0, 0, 1},
                {1, 0, 1, 0, 1, 1, 0, 1, 1},
                {1, 0, 0, 0, 1, 1, 1, 0, 1},
                {1, 0, 1, 0, 0, 0, 0,-1, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1}};
int nPast[N][N];// to save the path already walked
int sx=0,sy=0,ex=0,ey=0,cx=0,cy=0;// start x y, end x y,current x y
CStack *stkx=new CStack;// x position stack
CStack *stky=new CStack;// y position stack   

/////////////////////////////////////////////
// Functions
int MapIni()
{
    for (int i=0;i<N;i++)
        for (int j=0;j<N;j++)
        {
            if (nMap[i][j]==-1) {sx=j;sy=i;}
            if (nMap[i][j]==-2) {ex=j;ey=i;}
            nPast[i][j]=nMap[i][j];
        }
    nPast[sy][sx]=2;// Start point is waled.
    cx=sx;// save current position as start point
    cy=sy;  
    return 0;
}

int FindPath()
{
    stkx->Push(sx);
    stky->Push(sy);// Push start point
    while(nMap[cy][cx]!=-2)
    {
        // reset the current xy if already poped
        cy=stky->GetTop();cx=stkx->GetTop();
        
        // if next position can be walked and never walked before
        if      ((nMap[cy][cx+1]<1) && (nPast[cy][cx+1]!=2))
        {
            cx++;// Go right
            stkx->Push(cx);stky->Push(cy);//Push x y
            nPast[cy][cx]=2;// here already walked
        }
        else if ((nMap[cy-1][cx]<1) && (nPast[cy-1][cx]!=2))
        {// Go up
            cy--;
            stkx->Push(cx);stky->Push(cy);
            nPast[cy][cx]=2;
        }
        else if ((nMap[cy+1][cx]<1) && (nPast[cy+1][cx]!=2))
        {// Go down
            cy++;
            stkx->Push(cx);stky->Push(cy);
            nPast[cy][cx]=2;
        }
        else if ((nMap[cy][cx-1]<1) && (nPast[cy][cx-1]!=2))
        {// Go left
            cx--;
            stkx->Push(cx);stky->Push(cy);
            nPast[cy][cx]=2;
        }
        else {stkx->Pop();stky->Pop();}// no way to go: pop   
    }   
   
    return 0;
}  

void ShowPath()
{
    int t=0;
    while(!t)
    {
        nMap[stky->GetTop()][stkx->GetTop()]=8;
        stkx->Pop();
        t=stky->Pop();
    }
    nMap[sy][sx]=-1;
    nMap[ey][ex]=-2;   
    for (int i=0;i<N;i++)
    {    for (int j=0;j<N;j++)
        {
            if      (nMap[i][j]==0 )   printf (" ");
            else if (nMap[i][j]==8 )   printf (".");
            else if (nMap[i][j]==-1)   printf ("S");
            else if (nMap[i][j]==-2)   printf ("E");
            else  /*(nMap[i][j]==1 )*/ printf ("X");
        }
        printf("\n");
    }   
}  

void ShowMap()
{
    for (int i=0;i<N;i++)
    {    for (int j=0;j<N;j++)
        {
            if      (nMap[i][j]==0 )   printf (" ");
            else if (nMap[i][j]==8 )   printf (".");
            else if (nMap[i][j]==-1)   printf ("S");
            else if (nMap[i][j]==-2)   printf ("E");
            else  /*(nMap[i][j]==1 )*/ printf ("X");
        }
        printf("\n");
    }
}            
////////////////////////////////////
// Main
//
int main(int argc, char *argv[])
{

    MapIni();
    ShowMap();
    FindPath();  
    ShowPath();
    system ("pause");
    delete stkx;
    delete stky;
    return 0;
}
//另外,看了飞燕的论坛里面说寻路经的时候不用每个方向判断,用个什么DX就能处理了,我看不懂
//能不能请哪位大哥具体说明一下。
搜索更多相关主题的帖子: 迷宫 算法 
2008-04-12 15:33
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
那个什么。。。。。看不懂。新手在这里好难混阿。。。。。
2008-04-12 16:05
SNAKEQX
Rank: 1
等 级:新手上路
帖 子:112
专家分:3
注 册:2006-4-11
收藏
得分:0 
郁闷了,为什么大家写的代码就几行就解决了,我的要这么多行。谢谢孔明的代码,我要好好研究一段时间。
2008-04-12 16:52
快速回复:作为新手琢磨了一天,终于想出走迷宫的暴力算法。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.022756 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved