迷宫求解（数据结构栈应用）

[c++]代码库
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
 
#define INIT_SIZE 100 //存储空间初始分配量
#define SIZE_ADD 10  //存储空间分配增量
#define MAXLEN 10   //迷宫大小
 
struct Coord
{
      int r;
      int c;
      bool operator == (const Coord &b) const
      {
        return (r==b.r && c==b.c);
      }
};
 
struct Node
{
       int  ord;
       Coord seat;
       int  di;
};
struct MazeType
{
       int r;
       int c;
       char map[MAXLEN][MAXLEN];
};
int dir[][2]={1,0, -1,0, 0,1, 0,-1};
bool flag;
 
class Stack
{
    public:
        Stack ()
        {
            base = (Node *) malloc(INIT_SIZE * sizeof (Node));
                if (!base) exit(0);
            top = base;
            size = INIT_SIZE;
        }
        bool empty () const { return top==base; }
        void pop(Node &e);
        void push(Node a);
 
    private:
        Node * top;
        Node * base;
        int size;
};
 
void Stack::push(Node item)
{
    if (top - base >= size)
    {
        base = (Node *) realloc(base, (size+SIZE_ADD)*sizeof(Node));
        if (!base) exit(0);
        top = base + size;
        size += SIZE_ADD;
    }
    *top++ = item;
}
 
void Stack::pop(Node &e)
{
    if (top==base) return;
    e = * -- top;
}
 
void MadeMap (MazeType &maze)
{
 
    freopen ("test.in","r",stdin);
    flag = false;
    cin >> maze.r >> maze.c;
        for(int i=0; i<maze.r; i++)
              for(int j=0; j<maze.c; j++)
                   scanf (" %c",&maze.map[i][j]);
}      
 
 
Coord NextPos(Coord &curpos, int i)
{
 
      Coord ans;
      ans = curpos;
      ans.r += dir[i][0];
      ans.c += dir[i][1];
      return ans;
}
 
 
void MazePath(MazeType &maze, Coord start, Coord end)
{
      Stack S;
      Coord curpos;  //当前坐标
      Node e;
 
      curpos=start;
      int curstep=1;
 
      do
      {    
         if(maze.map[curpos.r][curpos.c]=='.')  //此路可通
         {
             maze.map[curpos.r][curpos.c]='*';
 
             e.ord=curstep;
             e.seat=curpos;
             e.di=1;
 
             S.push(e);
             if(curpos == end)
             {
                 flag = true;
                 return;
         　　 }
             curpos=NextPos(curpos,0);
             curstep++;                        
          }
          else
          {
               if(!S.empty())
               {
                    S.pop(e);
                    while(e.di==3 && !S.empty())
                          S.pop(e);
                    if(e.di < 4)
          　　      {
                         e.di++;
                         S.push(e);            
                         curpos=NextPos(e.seat,e.di);
                    }
                 }
             }
       }while(!S.empty());
}
 
void PrintMaze(MazeType &maze)
{
 
     if (flag)
     {
         cout << "迷宫路程图：\n";
         for(int i=0;i<maze.r;i++)
         {
            cout << "      ";
            for(int j=0;j<maze.c;j++)
                printf("%2c",maze.map[i][j]);
            cout << endl;
         }
      }
      else
          cout << "\n*****    次迷宫无法从起点走到终点。   ******\n\n";
}
 
int main()
{
 
    MazeType maze;
    Coord start,end;
        
    MadeMap (maze);
 
    start.r = start.c = 0;
    end.c = maze.c-1;
    end.r = maze.r-1;
 
    MazePath(maze, start, end);
    PrintMaze(maze);
    return 0;
}
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[c++]代码库

网友评论 (发表评论)

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
