迷宫求解问题

一．栈求解一条通路（可以判断是否有通路）
　　
#include<iostream>
#include<stack>
using namespace std;
#define m 6
#define n 8
int maze[8][10]={
        1,1,1,1,1,1,1,1,1,1,
        1,0,1,1,1,0,1,1,1,1,
        1,1,0,1,0,1,1,1,1,1,
        1,0,1,0,0,0,0,0,1,1,
        1,0,1,1,1,0,1,1,1,1,
        1,1,0,0,1,1,0,0,0,1,
        1,0,1,1,0,0,1,1,0,1,
        1,1,1,1,1,1,1,1,1,1
};
typedef struct {
    int x;
    int y;
}item;
item move[8]={
    {0,1},{1,1},{1,0},{1,-1},
    {-1,0},{-1,-1},{0,-1},{1,-1}
};
typedef struct {
    int x,y,d;
}SeqStack;
stack<SeqStack> s;
int path()
{
    while(!s.empty()) s.pop();
    int x,y,d,i,j;
    SeqStack temp;
    temp.x=1;
    temp.y=1;
    temp.d=-1;
    s.push(temp);
    while(!s.empty())
    {
        temp=s.top();
        s.pop();
        x=temp.x;
        y=temp.y;
        d=temp.d+1;
        while(d<8)
        {
            i=x+move[d].x;
            j=y+move[d].y;
            if(maze[i][j]==0)
            {
                //temp={x,y,d};
                temp.x=x;
                temp.y=y;
                temp.d=d;
                s.push(temp);
                x=i;
                y=j;
                maze[x][y]=-1;
                if(x==m && y==n)
                    return 1;
                else
                    d=0;
            }
            else
                d++;
        }
    }

    return 0;
}
int main()
{
    int i,j;
    //print maze
    for( i=2;i<8;i++)
    {
        for(j=2;j<10;j++)
            cout<<maze[i][j]<<" ";
        cout<<endl;
    }
    //print move
    for(i=0;i<8;i++)
        cout<<move[i].x<<" "<<move[i].y<<endl;
    cout<<(path()==1?"迷宫有路！\n":"迷宫无路！\n");
    SeqStack temp;
    while(!s.empty())
    {
        temp=s.top();
        s.pop();
        printf("(%d,%d,%d)-->",temp.x,temp.y,temp.d);
    }
    printf("\n");
    return 0;
}
Posted on 2009-06-07 19:32 北国飘雨 阅读(107) 评论(0)  编辑 收藏 引用 所属分类: ACM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理