bfs转弯问题-白红宇的个人博客

bfs转弯问题

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

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

hdu1175

题目链接；；

题目大意；就是转弯只能转两次；只能走0的地方；首末位置的数字要相同；这题还要注意减枝容易超时

hdu1728

题目链接；；

题目大意；给定转弯次数；问在要求内是否可以达到目的地；注意首末地址的输入方式；可以先进行处理；

NBUT；1642；

题目链接；；

题目大意；只看第二种情况；

要求每次都必须转弯；也就是说每个节点到下个节点的方向要不是相同的；这个有点点难理解；

题目源代码最后面摆出来;

分析；；；；；；

题型分类暂时把bfs法转弯问题分为两类；1；列如1175和1728的那种，限制了转弯的次数求最优解；2；列如1642；第二次bfs时每次都必须转弯

先看第一种；这个一样的可以套模板；转弯次数一定，那么我们就每次每个点方向搜索的时候把一个方向全部搜索完；搜索到尽头；

然后在出队列；后面照旧；如果达到了转弯次数还没有搜到就不能按要求搜到了；；；

可以自己模拟一下；看这部分代码实现；

这是1175的那部分代码；还要注意减枝一下while(!q.empty())    {        now=q.front();        q.pop();        if(now.x==x2&&now.y==y2&&now.w<=2)        {            return 1;        }        if(now.w>2)//减枝；；        {            //q.pop();            continue;        }        for(i = 0; i < 4; i++)        {            a=now.x+dir[i][0];            b=now.y+dir[i][1];            while(a>=1&&a<=n&&b>=1&&b<=m&&mp[a][b]==0)//一条方向走到底；；这里也是while；            {                if(mark[a][b]==0)                {                    next.x=a;next.y=b;next.w=now.w+1;                    mark[a][b]=1;                    q.push(next);                }                a+=dir[i][0];//在while内部；；；；                b+=dir[i][1];            }        }    }

方向问题的第一种就这样解决了；基本上可以套用这样的模板；

要在k次转弯内问是否可以达到要求；可以每次搜索方向的时候一条方向搜完；这样可以很好的解决这个问题；**要特别注意；**最先初始化方向次数，一般是为-1；这样才能保证；从起点开始的4个方向的节点都是0转弯；****先全部是不用转弯的；全部搜索一遍；达到要求的入队列；然后在在0转弯并且达到要求的点的前提下再搜索；每次都这样；看是否可以在k次之内在要求之内达到目的地；

第一种类型的说完了；看第二种类型的吧；

每次都要转弯；我看到这个知识点的时候就有两个东西一直搞混了；

我把方向搜索过程中的不同向和节点路径的转弯搞混淆了；

其实节点路径的转弯就跟我们普通的bfs那个标记路径是否重复类似的只是这里变成三维数组；标记方向是否重复；三维数组的第三维表示这个节点的这个方向是否走过；mark1[now.x][now.y][i]==0；就是看next.x，next.y的i方向是否走过；走过那么就会标记成1了；

而搜索方向就是；now.bj!=i；就是问上一节点的方向bj是否还是i如果是那么我们则不能再走这个方向了；

注意这两个方向都是；上个节点对要走的节点的方向；因此都是now，而不是next；这个要注意；

可以看代码了；对着代码理解吧；特别看那个if判断的方向判断；；；

就是1642的部分代码now.x=r1;now.y=l1;now.num=mp[r1][l1];now.bj=-1;    q.push(now);    while(!q.empty())    {        now = q.top();        q.pop();        for(i = 0; i < 4; i++)        {                next.x=now.x+dir[i][0];            next.y=now.y+dir[i][1];            if(next.x>=0&&next.x
   
    =0&&next.y

暂时关于转弯的bfs就到这了；

/*“连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。Input输入数据有多组。每组数据的第一行有两个正整数n,m(0
   
    <=1000,0
    
     <1000)，分别表示棋盘的行数与列数。在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0
     <50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。注意：询问之间无先后关系，都是针对当前状态的！*/ #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;//依据是转弯问题的bfs；套路依旧；一个方向走到底；不过这个题目容易超时所以要剪纸加限定条件//超时了几次，wa了几次；//没有减枝，没有考虑是同一点的情况；bfs时终点没有先处理一下；；；int mp[1005][1005];int mark[1005][1005];int n, m,x1,x2,y11,y2;struct node{ int x, y,w;};int dir[4][2]={ { 1,0},{ 0,1},{-1,0},{ 0,-1}};int bfs(){ mp[x2][y2]=0;//处理终点；；因为下面要搜到终点，因此要处理一下；；； int i, a,b; memset(mark,0,sizeof(mark)); queue
              
                q; node now,next; now.x=x1;now.y=y11;now.w=-1;//依据处理为-1； mark[x1][y11]=1; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(now.x==x2&&now.y==y2&&now.w<=2) { return 1; } if(now.w>2)//减枝；； { //q.pop(); continue; } for(i = 0; i < 4; i++) { a=now.x+dir[i][0]; b=now.y+dir[i][1]; while(a>=1&&a<=n&&b>=1&&b<=m&&mp[a][b]==0)//一条方向走到底；； { if(mark[a][b]==0) { next.x=a;next.y=b;next.w=now.w+1; mark[a][b]=1; q.push(next); } a+=dir[i][0]; b+=dir[i][1]; } } } return 0;}int main(){ int i, j, tt,p; while(~scanf("%d %d",&n, &m)) { if(n==0&&m==0) break; for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) scanf("%d",&mp[i][j]); } scanf("%d",&tt); while(tt--) { scanf("%d %d %d %d",&x1,&y11,&x2,&y2); //mp[x2][y2]=0; if((mp[x1][y11]!=mp[x2][y2])||(mp[x1][y11]==0))//减支处理；；； { printf("NO\n"); } else if(x1==x2&&y11==y2) printf("NO\n"); else { p = bfs(); mp[x2][y2]=mp[x1][y11]; if(p==1) { printf("YES\n"); } else printf("NO\n"); } } } return 0;}

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;//hdu1728;bfs限制条件为转弯次数限制不大于k；因此bfs搜索时要有个方向走到底；意思就是说队列不是相邻距离存放的而是一个方向的存放；//还有就是要注意输入；输入字符串的时候要注意；（下面以注释）//注意他参数的输入；先列再行；所以要记得处理一下；//对于队列压入的问题；将这个元素((结构体)压入队列；则这个元素原有的值也不存在了；；；(这个bug搞了好久；）int s1,s2,e1,e2,k,n,m;char mp[105][105];int mark[105][105];struct node{ int x, y,w;};int dir[4][2]={ { 1,0},{ 0,1},{-1,0},{ 0,-1}};void bfs(){ int i; queue
            
              q; memset(mark,0,sizeof(mark)); node now,next; now.x=s1;now.y=s2;now.w=-1; mark[now.x][now.y] = 1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==e1&&now.y==e2&&now.w<=k) { printf("yes\n"); return ; } for(i = 0; i < 4; i++) { int a=now.x+dir[i][0]; int b=now.y+dir[i][1]; while(a>=0&&a
             
              =0&&b

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include 
        
         using namespace std;int mp[505][505];int n, m, r1,r2,l1,l2;struct node{ int x, y, num,bj; friend bool operator<(node a, node b) { return a.num>b.num;}};int dir[4][2]={ { 1,0},{ 0,1},{-1,0},{ 0,-1}};int mark1[505][505][4];bool bfs()//第二种；；； { int i; priority_queue
         
           q; node now,next; memset(mark1,0,sizeof(mark1)); now.x=r1;now.y=l1;now.num=mp[r1][l1];now.bj=-1; q.push(now); while(!q.empty()) { now = q.top(); q.pop(); for(i = 0; i < 4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x>=0&&next.x
          
           =0&&next.y
           
             q; node now,next; int mark[505][505]={0}; now.x=r1;now.y=l1;now.num=mp[r1][l1]; mark[r1][l1]=1; q.push(now); while(!q.empty()) { now = q.top(); q.pop(); for(i = 0; i < 4; i++) { next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1]; if(next.x>=0&&next.x
            
             =0&&next.y
             
              ='0'&&ch[j]<='9') { num = ch[j]-'0'; if(ch[j+1]>='0'&&ch[j+1]<='9') { num = num*10+(ch[j+1]-'0'); j++; if(ch[j+1]>='0'&&ch[j+1]<='9') { num = num*10+(ch[j+1]-'0'); j++; } } mp[i][l]=num; l++; } } } printf("Case %d: ",kk++); if(bfs2()==0) { printf("-1 "); } int aa=bfs(); if(aa==0) { printf("-1\n"); } //printf("iwdffuf\n"); } return 0 ;}

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

上一篇：bfs三维地图

下一篇：模拟题2（打表）

发表评论

关于作者

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

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章