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

倚楼听风雨

没有理想的人,永远也不能翱翔与蓝天白云之上~

 
 
 

日志

 
 

一个迷宫求解问题(C++)  

2007-11-22 23:49:58|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

#include<iostream.h>
#include <iomanip.h>
#define m 6
#define n 6
#define maxsize 100
int mg[m+1][n+1]={
 {1,1,1,1,1,1},
 {1,0,0,0,1,1},
 {1,0,1,0,0,1},
 {1,0,0,0,1,1},
 {1,1,0,0,0,1},
 {1,1,1,1,1,1}
};
struct{
 int i,j;
 int di;
} Stack[maxsize],Path[maxsize];
int top=-1;
int count=1;
int minlen=maxsize;
void mgpath()
{
 int i,j,di,find,k;
 top++;
 Stack[top].i=1;
 Stack[top].j=1;
 Stack[top].di=-1;
 mg[1][1]=-1;
 while(top>-1)
 {
  i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
  if(i==m-2 && j==n-2)
  {
   cout<<setw(4)<<count++;
   for(k=0;k<=top;k++)
   {
    cout<<" ("<<Stack[k].i<<","<<Stack[k].j<<")";
    if((k+1)%5==0)
     cout<<endl;
   }
   cout<<endl;
   if(top+1<minlen)
   {
    for(k=0;k<=top;k++)
    Path[k]=Stack[k];
    minlen=top+1;
   }
   mg[Stack[top].i][Stack[top].j]=0;
   top--;
   i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
  }
  find=0;
  while(di<4 && find==0)
  {
   di++;
    switch(di)
   {
    case 0: i=Stack[top].i-1;j=Stack[top].j;
     break;
    case 1: i=Stack[top].i;j=Stack[top].j+1;
     break;
    case 2: i=Stack[top].i+1;j=Stack[top].j;
     break;
    case 3: i=Stack[top].i-1;j=Stack[top].j-1;
     break;
   }
   if(mg[i][j]==0)
    find=1;
  }
  if(find==1)
  {
   Stack[top].di=di;
   top++;
   Stack[top].i=i;
   Stack[top].j=j;
   Stack[top].di=-1;
   mg[i][j]=-1;
  }
  else
  {
   mg[Stack[top].i][Stack[top].j]=0;

   top--;
  }
 }
 cout<<"最短路径如下:"<<endl;
 cout<<"长度:  "<<minlen<<endl;
 for(k=0;k<minlen;k++)
 {
  cout<<" ("<<Stack[k].i<<","<<Stack[k].j<<")";
  if((k+1)%5==0)
  cout<<endl;
 }
 cout<<endl;
}
void main()
{
 cout<<"迷宫路径如下:\n";
 mgpath();
}
 

  评论这张
 
阅读(245)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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