[数据结构] 迷宫问题（栈和队列，深搜和广搜）-白红宇

[数据结构] 迷宫问题（栈和队列，深搜和广搜）

阅读量：5863 次

发布时间：2019-06-19

本文共 1596 字，大约阅读时间需要 5 分钟。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int dx[4]={0,-1,1,0};//方向int dy[4]={-1,0,0,1};bool vis[6][6];int total=0;//多少可到达路径int sx=1,sy=1;//入口出口坐标int ex=4,ey=4;int num[10][10];//广搜时记录到达当前点的最少步数struct P{    int x,y;}point[40];//用来记录可到达路径struct PP{    int fx,fy;}path[10][10];//用来记录最短路径坐标增量，用于回溯输出最短路径char map[6][6]=//地图{    {'#','#','#','#','#','#'},    {'#','.','.','.','#','#'},    {'#','.','#','.','.','#'},    {'#','.','.','.','#','#'},    {'#','#','.','.','.','#'},    {'#','#','#','#','#','#'}};bool ok(int x,int y)//判断当前点是否可走{    if(x<0||x>5||y<0||y>5)        return 0;    if(map[x][y]=='#')        return 0;    if(vis[x][y]==1)        return 0;    return 1;}void dfs(int x,int y,int step)//深搜可到达路径，参数step对于记录路径来说很重要{    if(x==ex&&y==ey)    {        total++;        cout<<"第"<
         
          <<"条路径为: "; for(int i=0;i
          
           q; P a,b; a.x=x; a.y=y; path[a.x][a.y].fx=0;path[a.x][a.y].fy=0; q.push(a); while(!q.empty()) { b=q.front(); q.pop(); for(int i=0;i<4;i++) { a.x=b.x+dx[i]; a.y=b.y+dy[i]; if(ok(a.x,a.y)) { vis[a.x][a.y]=1; q.push(a); path[a.x][a.y].fx=dx[i]; path[a.x][a.y].fy=dy[i]; num[a.x][a.y]=num[b.x][b.y]+1;//记录步数 } } }}void print(int x,int y)//输出最短路径{ if(x==sx&&y==sy) { cout<<"(1,1)"; return; } print(x-path[x][y].fx,y-path[x][y].fy); cout<<"("<
           
            <<","<
            
             <<")";}int main(){ memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); vis[sx][sy]=1; point[0].x=sx;point[0].y=sy; dfs(sx,sy,1); cout<<"总计有"<
             
              <<"条可到达路径"<