HDU 2102 A计划（BFS+细节维护）-白红宇的个人博客

发布日期：2021-05-14 14:38:03 浏览次数：20 分类：精选文章

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

一道很裸的BFS，看时间复杂度看可以用DFS+剪枝就很神奇。

第一次做的时候维护了很多量，比如时间在此题中是一个重要的量，但是不用时刻维护，只需要维护走到当前位置需要多少天，最后找到P是多少天（如果能的话），比较找到P的天数和给定的天数即可。还有一个问题就是图的构建，开始我将N开大两倍，发现这样做有很严重的边界判断问题，容易出现bug还使得代码量增加，直接再开一维能够避免上述情况。此题还有一个教训是hdu上有个误导性样例，除非万不得已不要看discuss，简直有毒。

总之此题走出了很多坑，是到不错的题目，BFS代码量比较多，但是先想清楚怎么样做能使得代码量尽可能小，尽可能简单是写之前需要想的事情，不要一看到就动手，先分析一波。

#include
   
    #include
    
     #include
     
      using namespace std;struct node{       int x,y,c;    bool d;};queue
      
        q;char a[15][15][2];int vis[15][15][2];int dx[4]={   0,0,1,-1};int dy[4]={   1,-1,0,0};int n,m,k;int main(){       int t;    scanf("%d",&t);    while(t--){           scanf("%d%d%d",&n,&m,&k);        for(int p=0;p<2;p++){               for(int i=1;i<=n;i++){                   for(int j=1;j<=m;j++){                       scanf("\n\n%c",&a[i][j][p]);                }            }        }        bool as=0;        vis[1][1][0]=1;        node ne;        ne.x=1;ne.y=1;ne.c=0;ne.d=0;        q.push(ne);        int cnt;        while(!q.empty()){               node z;            z=q.front();            q.pop();            if(a[z.x][z.y][z.d]=='P'){                   cnt=z.c;                as=1;                break;            }            for(int i=0;i<4;i++){                   int xx=z.x+dx[i];                int yy=z.y+dy[i];                if(xx>=1&&xx<=n&&yy<=m&&yy>=1&&!vis[xx][yy][z.d]&&a[xx][yy][z.d]!='*'){                       if(a[xx][yy][z.d]=='.'||a[xx][yy][z.d]=='P'){                           node f;                        f.x=xx;                        f.y=yy;                        f.c=z.c+1;                        f.d=z.d;                        vis[xx][yy][z.d]=1;                        q.push(f);                    }                    if(a[xx][yy][z.d]=='#'&&a[xx][yy][!z.d]!='#'&&a[xx][yy][!z.d]!='*'&&!vis[xx][yy][!z.d]){                           node f;                        f.x=xx;                        f.y=yy;                        f.c=z.c+1;                        f.d=!z.d;                        vis[xx][yy][!z.d]=1;                        q.push(f);                    }                }            }        }        if(!as||cnt>k)printf("NO\n");        else printf("YES\n");        memset(vis,0,sizeof(vis));        memset(a,0,sizeof(a));        while(!q.empty())q.pop();    }}

上一篇：Uva 1220 Party at Hali-Bula（最大独立子集问题）

下一篇：null和undefined的区别

发表评论

关于作者

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

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章