注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zjushuiping

追求的只是心中的那一份宁静!

 
 
 

日志

 
 

迷宫问题求解  

2010-08-12 14:49:28|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
#include <cstdlib>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define MAZE_INIT_SIZE 50
using namespace std;
struct P{
       int row;
       int col;
       int pre;
       };

struct MAZE{
       char m[MAZE_INIT_SIZE][MAZE_INIT_SIZE];
       int row,col;
       P s;//起点
       P e;//终点
       };
       
int f_row[4]={1,-1,0,0};
int f_col[4]={0,0,1,-1};
       
int check(int i,int j,struct MAZE maze)//判断
{
    
    if(i<0||j<0||i>=maze.row||j>=maze.col)
    return 0;
    if(maze.m[i][j]=='o')
    return 1;
    return 0;
}
void search(struct MAZE &maze);    
void maze_game()
{
     struct MAZE maze;
     
     printf("%15s","");
     cout<<"请输入迷宫的行数...";
     cin>>maze.row;
     while(maze.row<1)
     {printf("%15s","");cout<<"输入错误,请重新输入...";cin>>maze.row;}
     
      
              
     printf("%15s","");
     cout<<"请输入迷宫的列数...";
     cin>>maze.col;
     while(maze.col<1)
     {printf("%15s","");cout<<"输入错误,请重新输入...";cin>>maze.col;}
     system("cls");
     printf("%15s","");cout<<"注意:坐标从0开始...\n";
     printf("%15s","");
     cout<<"请输入迷宫的起始点坐标...";
     cin>>maze.s.row;
     cin>>maze.s.col;
     maze.s.pre=-1;
     while(maze.s.row<0||maze.s.col<0||maze.s.row>=maze.row||maze.s.col>=maze.col)
     {printf("%15s","");cout<<"输入错误,请重新输入...";cin>>maze.s.row>>maze.s.col;}
      
     printf("%15s","");
     cout<<"请输入迷宫的起始点坐标...";
     cin>>maze.e.row;
     cin>>maze.e.col;
     maze.e.pre=-1;
     while(maze.e.row<0||maze.e.col<0||maze.e.col>=maze.col||maze.e.row>=maze.row)
     {printf("%15s","");cout<<"输入错误,请重新输入...";cin>>maze.e.row>>maze.e.col;}
      system("cls");
     //printf("%15s","");
     cout<<"请输入迷宫地形,o表示空地#表示墙壁...\n";
     
     int i,j;
     for(i=0;i<maze.row;i++)
     for(j=0;j<maze.col;j++)
     {/*printf("\n%15s","");*/cin>>maze.m[i][j];}
     /*cout<<maze.row<<endl<<maze.col<<endl;
     cout<<maze.s.row<<' '<<maze.s.col<<endl;
     cout<<maze.e.row<<' '<<maze.e.col<<endl;
     for(i=0;i<maze.row;i++)
     {for(j=0;j<maze.col;j++)
      cout<<maze.m[i][j];
      cout<<endl;
     }*/
     search(maze);
}
void output(int end,P sq[]);
void search(struct MAZE &maze)
{
     P sq[MAZE_INIT_SIZE*MAZE_INIT_SIZE];
     int begin=0,end=1;
     maze.m[maze.s.row][maze.s.col]='#';
     sq[0].pre=-1;
     sq[0].row=maze.s.row;
     sq[0].col=maze.s.col;
     int i,j,k;
     while(begin<end)
     {
                     for(k=0;k<4;k++)
                     {
                                     i=sq[begin].row+f_row[k];
                                     j=sq[begin].col+f_col[k];
                                     if(check(i,j,maze))
                                     {sq[end].row=i;
                                      sq[end].col=j;
                                      sq[end].pre=begin;
                                      maze.m[i][j]='#';
                                      
                                      if((i==maze.e.row)&&(j==maze.e.col))
                                      {
                                       system("cls");
                                       printf("%5s","");cout<<"路径...\n";
                                       printf("%5s","");
                                       output(end,sq);
                                       cout<<endl;
                                       return ;
                                      }
                                      end++;
                                     }
                     }
                     begin++;
     }
     system("cls");
     printf("%15s","");
     cout<<"没有可达路径";
}


void output(int end,P sq[])//输出
{
     if(end==0)
     {cout<<"("<<sq[end].row<<","<<sq[end].col<<")";return ;}
     
     if(end>0)
     {output(sq[end].pre,sq);cout<<"-->("<<sq[end].row<<","<<sq[end].col<<")";return ;}
}
     
     
                         
                                      
                                      
                     
                     
     
     
                            
      



int main(int argc, char *argv[])
{maze_game();
    system("PAUSE");
    return EXIT_SUCCESS;
}
  评论这张
 
阅读(80)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017