BFS的一个题-白红宇的个人博客

BFS的一个题

发布日期：2022-02-08 04:20:48 浏览次数：3 分类：技术文章

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

关于 BFS要点：

1、若为可化为的坐标系图形，可用结构体存储其x值，y值和步数。（一般开now 和 next ，now用于取出队列里面的结构体）next用于上下左右的运动计算，并且push到队列中。

2、在运用队列时，常用的函数（push，front，size，empty，pop 等等），特别是在front队列里面的结构体时记住pop，队列里面的内容是先存放先使用，有序取出。

3、在压入点到队列中时要进行判断是否合理，可写一个函数check进行判断，判断依据是否出界，以及是否合题意要求。

4、题目A计划中的”传送门“并不会影响step，在判断过于复杂时可以写函数以免混淆思维。在关键点可以用数组进行记录，开数组时可以根据题意开大10%的数组（题意：a<=100 可开a[110]）。

5、在移动压缩时，可根据题意开一个二维数组进行前后左右的移动，移动时一般使用next结构体。

BFS例题：

A计划

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主，因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚，告招天下勇士来拯救公主。不过公主早已习以为常，她深信智勇的骑士LJ肯定能将她救出。

现据密探所报，公主被关在一个两层的迷宫里，迷宫的入口是S（0，0，0），公主的位置用P表示，时空传输机用#表示，墙用*表示，平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置，但如果被转到的位置是墙的话，那骑士们就会被撞死。骑士们在一层中只能前后左右移动，每移动一格花1时刻。层间的移动只能通过时空传输机，且不需要任何时间。

Input输入的第一行C表示共有C个测试数据，每个测试数据的前一行有三个整数N，M，T。 N，M迷宫的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况，后N*M表示迷宫第二层的布置情况。Output如果骑士们能够在T时刻能找到公主就输出“YES”，否则输出“NO”。Sample Input

15 5 14S*#*..#........****....#...*.P#.*..***.....*.*.#..

Sample Output

YES

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct node{    int x,y,floor;    int step;};int t,n,m,lim;int s[3],e[3];int to[4][2] = {1,0,0,1,-1,0,0,-1};char map[2][15][15];int use[2][15][15];int check(int floor,int x,int y){    if(x<0 || y<0 || x>=n || y>=m)        return 1;    if(map[floor][x][y]=='*')        return 1;    return 0;}void BFS(){    memset(use,0,sizeof(use));    node a,next;    queue
      
        Q;    int i,j,k;    a.floor = s[0];    a.x = s[1];    a.y = s[2];    a.step = 0;    use[s[0]][s[1]][s[2]] = 1;    Q.push(a);    while(!Q.empty())    {        a = Q.front();        Q.pop();        if(a.floor == e[0] && a.x == e[1] && a.y == e[2])        {            printf("YES\n");            return ;        }        if(a.step>=lim)            break;        for(i = 0; i<4; i++)        {            next = a;            next.x+=to[i][0];            next.y+=to[i][1];            next.step++;            if(check(next.floor,next.x,next.y))                continue;            if(use[next.floor][next.x][next.y])                continue;            use[next.floor][next.x][next.y] = 1;            if(map[next.floor][next.x][next.y] == '#')            {                next.floor=!next.floor;                if(check(next.floor,next.x,next.y))                    continue;                if(use[next.floor][next.x][next.y])                    continue;                if(map[next.floor][next.x][next.y] == '*' || map[next.floor][next.x][next.y] == '#')                    continue;                use[next.floor][next.x][next.y] = 1;            }            if(next.floor == e[0] && next.x == e[1] && next.y == e[2])            {                printf("YES\n");                return ;            }            Q.push(next);        }    }    printf("NO\n");}int main(){    int i,j,k;    scanf("%d",&t);    while(t--)    {        scanf("%d%d%d",&n,&m,&lim);        for(int k=0;k<2;k++)        {            for(i=0;i

注意点：如果两层的相同位置都是传送门，那么就会无限传送；

思路：

因为被转到的位置是墙的话，骑士们就会被撞死，如果两层的相同位置都是传送门，那么就会无限传送，我们可以提前做预处理，把这两种情况的点都设为墙，就不会干涉到后面的搜索；

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;struct node{   int t,x,y,z;};char map[15][15][5];int mark[15][15][5];int n,m,t,flag;int dx,dy,dz;int vis[4][2]={0,1,0,-1,1,0,-1,0};int ok(int x,int y,int z){    if(x>=1&&x<=n&&y>=1&&y<=m&&map[x][y][z]!='*')       return 1;    else       return 0;}void bfs(){    node q,p;    q.x=1,q.y=1,q.z=1,q.t=0;    queue
       
        que;    que.push(q);    while(que.size())    {        q=que.front();        que.pop();        if(q.t>t)           return;        if(q.x==dx&&q.y==dy&&q.z==dz)        {            flag=q.t;            return;        }        for(int i=0;i<=3;i++)        {            p.x=q.x+vis[i][0];            p.y=q.y+vis[i][1];            if(ok(p.x,p.y,q.z)&&!mark[p.x][p.y][q.z])            {                mark[p.x][p.y][q.z]=1;                if(map[p.x][p.y][q.z]=='#')                {                    if(q.z==1)                       p.z=2;                    else                       p.z=1;                    mark[p.x][p.y][p.z]=1;                }                else                  p.z=q.z;                p.t=q.t+1;                que.push(p);            }        }    }}int main(){    int T;    scanf("%d",&T);    while(T--)    {        flag=0;        scanf("%d%d%d",&n,&m,&t);        getchar();        for(int j=1;j<=2;j++)        {            for(int i=1;i<=n;i++)            {                for(int k=1;k<=m;k++)                {                    scanf("%c",&map[i][k][j]);                    if(map[i][k][j]=='P')                       dx=i,dy=k,dz=j;                }                getchar();            }            getchar();        }        for(int i=1;i<=n;i++)           for(int j=1;j<=m;j++)           {               if(map[i][j][2]=='#'&&map[i][j][1]=='#')                  map[i][j][1]='*',map[i][j][2]='*';               if(map[i][j][2]=='#'&&map[i][j][1]=='*')                  map[i][j][2]='*';               if(map[i][j][1]=='#'&&map[i][j][2]=='*')                  map[i][j][1]='*';           }        memset(mark,0,sizeof(mark));        mark[1][1][1]=1;        bfs();        if(flag)           printf("YES\n");        else           printf("NO\n");    }}

分析

只需要注意双层之间传递的问题

如果‘#’的下一层是‘’那么这一层的‘#’也将变为‘ * ’

额外注意的一点就是关于两层的表示问题

如果一层是 ff 另一层就是 ff ^ 1；

代码 + 注释

#include 
   
    #include 
    
     #include
     
      using namespace std ;typedef struct L{    int x,y,f ;    int step ;}L ;int n,m,t ;char map[2][11][11] ;int vis[2][11][11] ;int dir[4][2]={
  {1,0},{-1,0},{0,1},{0,-1}} ;// 四个移动方向int flag ;void bfs(){    memset(vis,0,sizeof(vis)) ;    flag=0 ;    L now,next ;    queue 
      
        q ;//新建队列    now.x=now.y=now.f=now.step=0 ;    q.push(now) ;    vis[0][0][0]=1 ;    while(!q.empty())    {        now=q.front() ;        q.pop() ;        if(map[now.f][now.x][now.y]=='P' && now.step<=t)//如果搜寻到 目标值且步数少于等于最大值        {            flag=1 ;            return ;//标记 返还        }        if(map[now.f][now.x][now.y]=='P')//如果找到但是不是最大值  直接返回 无要求解（bfs默认为最小）        {            return ;        }        for(int i=0;i<4;i++)        {            next.x=now.x+dir[i][0] ;            next.y=now.y+dir[i][1] ;            next.f=now.f ;            int xx=next.x ;            int yy=next.y ;            int ff=next.f ;//变换之后的三维坐标            if(xx<0 || xx>=n)//判断是否越界                continue ;            if(yy<0 || yy>=m)                continue ;            if(map[ff][xx][yy]=='*')//判断是否是星号                continue ;            if(map[ff][xx][yy]=='#' && map[ff^1][xx][yy]=='*')//如果是电梯 那么他转换后是否是星号                continue ;            if(map[ff][xx][yy]=='#' && map[ff^1][xx][yy]=='#')//同样是电梯的也不行                continue ;                if(!vis[ff][xx][yy] && map[ff][xx][yy]=='#' && vis[ff^1][xx][yy]==0)            {                vis[ff][xx][yy]=1 ;                next.f^=1 ;//如果是电梯 转换到另外一层                vis[next.f][xx][yy]=1 ;//标记                next.step=now.step+1 ;//不失加一                q.push(next) ;//递归            }            if(!vis[ff][xx][yy] && map[ff][xx][yy]!='#')            {                vis[ff][xx][yy]=1 ;//标记                next.step=now.step+1 ;//步数加一                q.push(next) ;//递归            }        }    }}int main(void){    int c ;    scanf("%d",&c) ;    while(c--)    {        scanf("%d%d%d%*c",&n,&m,&t) ;        for(int i=0;i<2;i++)        {            for(int j=0;j

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

上一篇：初识BFS

下一篇：错位排序

发表评论

关于作者

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

-- 愿君每日到此一游！

分析

代码 + 注释

发表评论

最新留言

关于作者

推荐文章