bfs特殊方向-白红宇的个人博客

bfs特殊方向

发布日期：2021-06-29 11:10:42 浏览次数：3 分类：技术文章

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

hdu1548；

题目链接；；

题目大意；电梯问题；只有两个方向；上下；

hdu1372

题目链接；；

题目大意；象棋里面马走向的问题；方向就是马走日的方位；

例如1548；

电梯；每层楼都有一个值；这个值就是在这层楼可以通过电梯上这么多层或者下这么多层；问从a层是否可以到达b层；

套用模板就是把for循环改成两个if而已；

mark[now.x] = 1;    q.push(now);    while(!q.empty())    {        now = q.front();        q.pop();        if(now.x==b)//判断放前面；防止a==b的情况；        {            return now.step;        }        next.x=now.x-mp[now.x];        if(next.x>=1&&next.x<=n&&mark[next.x]==0)        {            mark[next.x] = 1;            next.step = now.step+1;            q.push(next);        }        next.x=now.x+mp[now.x];        if(next.x>=1&&next.x<=n&&mark[next.x]==0)        {            mark[next.x] = 1;            next.step = now.step+1;            q.push(next);        }    }    return -1;

列如；1372；

就是简单的套模板就是把方向改变一下；在纸上模拟一下马日的走向；；；

int dir[8][2]={
  {-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};

代码；

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;//两种移动方式；//之前把没有考虑a==b的情况一直wa；int n, a, b,bs;int mp[205];int mark[205];struct node{ int x,step;};int bfs(){ queue
            
              q; node now,next; memset(mark,0,sizeof(mark)); now.x = a;now.step=0; mark[now.x] = 1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==b)//判断放前面；防止a==b的情况； { return now.step; } next.x=now.x-mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } next.x=now.x+mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } } return -1;}int main(){ int i; while(~scanf("%d",&n)&&n!=0) { scanf("%d %d",&a,&b); for(i = 1; i <= n; i++) { scanf("%d",&mp[i]); } printf("%d\n",bfs()); } return 0;}

第二道

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;//只是8个方向不同而已；没有限制条件；int s1,s2,e1,e2,bs;struct node{ int x,y,t;};int mark[10][10];int dir[8][2]={ {-2,-1},{-1,-2},{ 1,-2},{ 2,-1},{ 2,1},{ 1,2},{-1,2},{-2,1}};void bfs(){ int i; queue
            
             q; memset(mark,0,sizeof(mark)); node now, next; now.x=s1;now.y=s2;now.t=0; mark[now.x][now.y]=1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==e1&&now.y==e2) { bs = now.t; return ; } for(i = 0; i < 8; i++) { next.x = now.x+dir[i][0]; next.y = now.y+dir[i][1]; if(next.x>=1&&next.x<=8&&next.y>=1&&next.y<=8&&mark[next.x][next.y]==0) { mark[next.x][next.y] = 1; next.t = now.t+1; q.push(next); } } } return ;}int main(){ char a1 ,b1; int a2,b2; while(~scanf("%c%d %c%d",&a1,&a2,&b1,&b2)) { getchar(); s1 = a1-96;s2=a2; e1 = b1-96;e2=b2; bfs(); printf("To get from %c%d to %c%d takes %d knight moves.\n",a1,a2,b1,b2,bs); } return 0;}

转载地址：https://blog.csdn.net/zw1996/article/details/52225000 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：并查集求————代数(就是到祖先的代数)

下一篇：bfs三维地图

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章