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

zxj015

 
 
 

日志

 
 

hdu 1372 Knight Moves bfs搜索  

2011-03-22 20:26:21|  分类: 搜索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给定棋盘上的两个点,求马从起点走到终点所需的最小步数,马的走法如下(和象棋差不多),本题也是简单的BFS搜索。
hdu 1372 Knight Moves bfs搜索 - 某年某月 - zxj015的博客

 
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
int xf,yf,xt,yt,ans;
int dir[8][2]={{-2,1},{2,1},{-2,-1},{2,-1},{-1,2},{1,2},{-1,-2},{1,-2}};
bool visited[9][9];
struct node
{
       int x,y;
       int time;
};
void bfs()
{
     int i,a1,b1,front=-1,rear=-1,xx,yy;
     node in,out;
     queue<node>que;
     in.x=xf;
     in.y=yf;
     in.time=0;
     que.push(in);
     visited[xf][yf]=true;
     while(!que.empty())
     {
       out=que.front();
       que.pop();
       if(out.x==xt&&out.y==yt)
       {
         ans=out.time;
         return;
       }
       for(i=0;i<8;i++)
       {
         xx=out.x+dir[i][0];
         yy=out.y+dir[i][1];
         if(xx<0||yy<0||xx>7||yy>7||visited[xx][yy])
          continue;
         in.x=xx;
         in.y=yy;
         in.time=out.time+1;
         visited[xx][yy]=true;
         que.push(in);
       }
     }
}
       
main()
{
      int i,j,flag,a,b;
      char c1,ci,c2;
      while(scanf("%c%d%c%c%d",&c1,&xf,&ci,&c2,&xt)!=EOF)
      {
         getchar();
         memset(visited,false,sizeof(visited));
         yf=c1-97;
         yt=c2-97;
         xf--;xt--;
         bfs();
         printf("To get from %c%d to %c%d takes %d knight moves.\n",c1,++xf,c2,++xt,ans);
      }
}

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

历史上的今天

评论

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

页脚

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