devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

（c语言实现）算法笔记之bfs及pta习题_奇怪的电梯pta

作者：知新_RL | 2024-04-18 10:06:04

赞

踩

奇怪的电梯pta

目录

一，bfs（广度优先搜索）的定义

二,bfs(广度优先搜索)的应用

三，题型训练

1，奇怪的电梯

2，寻宝 

3，龙舌兰酒吧 

四，总结 


       

一，bfs（广度优先搜索）的定义

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

以上资料来自于BFS（图论） - OI Wiki (oi-wiki.org)

 说点人话环节（doge）：比如走迷宫，我们一开始肯定会有一个起始位置，而之后改如何走是不太确定的，因为有四个方向可以走，广搜就是，一次搜索就走这四个方向，搜过的点就标记一下，下次不要再回去找（所以这里会标记起始的点，而由起始点走出的四个点还没有搜索，所以不必标记）。之后再从走出的四个点分别进行搜索接下去的四个方向的点。由一次搜索走出来的所有点就是一层。在每次走完一层之后，就先判定一下这一层的点有没有所需要的答案，如果有，那么就不需要再找了。

在图上就是，以V1为起点，第一次搜索就搜V2，V3,并将V1标记。此为一层，这时，应该先判断一下V2,V3是不是我们所需要的点，如果不是，那么就继续，往下搜索V4,V5,V6,V7. 直到找到目标。

那这时候就有人要问了：那找不到怎么办？也有走不通的迷宫啊！

回答这个问题之前，我们要先想想，bfs搜索的时候，数据要放到哪里？我们想想，每一次搜索的时候是不是就是先将要搜索的点放入储存的结构中，然后搜索完标记并退出。这符合“先进先出”的特点，也就是队列的特点。由于只会c语言我们只能去模拟队列的实现。如何模拟呢？用一个数组和两个指针变量就可以了。

    struct node queque[10000];
    memset(queque,0,sizeof(queque));
    int head=0,end=1;

就可以模拟队列的实现，当然，如果要使用模拟循环队列也是可以的。（记得加个判断，end>数组长度时，重置即可）但是要主要开好足够的空间 ，不然可能还没搜索，那一层的部分数据就会被覆盖掉。

因为一层一层搜索，所以如果还能走，必然有数据入队，自然就不会出现head>=end的情况（如果是循环队列，那么判断条件应该是head！=end，即head不会与end相等）。一旦出现上述情况，那么就说明没得搜了，已经都走遍了，如果此时还没找到答案，那么就是没有答案了。

二,bfs(广度优先搜索)的应用

目前我所遇到的基本上bfs的应用在于寻找最短路径类，之后如果有遇到其他的应用，会再写一篇文章来描述新的应用。

那么这里就以走迷宫为例，看看如何实现吧。

首先肯定要创建好结构体记录每次走的点，并创建好队列

struct node
{
    int num;
    int i;
    int j;
};

    struct node queque[10000];
    memset(queque,0,sizeof(queque));
    int head=0,end=1;

 然后创建走的四个方向

int local[][2]=
{
    {0,1},
    {0,-1},
    {1,0},
    {-1,0}
};

之后就是主体部分的实现了

int tmp=end;
        while(head<tmp)//一层搜索
        {
           for(int i=0;i<4;i++)//每个点搜索四个方位
           {
               int tmpi=queque[head].i+local[i][0];
               int tmpj=queque[head].j+local[i][1];
               if(tmpi<0||tmpi>=n||tmpj<0||tmpj>=m)//判断边界条件
               {
                   continue;
               }
               else if(arr[tmpi][tmpj]==-1)//搜索过的或者不可走点
               {
                   continue;
               }
               else
               {
                   //存下数值和地址，并将其入队
                   queque[end].num=arr[tmpi][tmpj];
                   queque[end].i=tmpi;
                   queque[end].j=tmpj;
                   end++;
                   arr[tmpi][tmpj]=-1;
               }
           }
            head++;
        }

三，题型训练

1，奇怪的电梯

 c大楼有一个一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 i 层楼 (1≤i≤N) 上有一个数字Ki(0≤Ki≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3,3,1,2,5 代表了Ki (K1=3,K2=3,…)，在1楼，按“上”可以到4楼，按“下”是不起作用的，因为没有−2楼。那么，从A楼到B楼至少要按几次按钮呢？

输入格式:

第一行包含3个用空格隔开的正整数，分别表示N,A,B (1≤N≤200,1≤A,B≤N) 。 第二行包含N 个用空格隔开的非负整数，表示Ki 。

输出格式:

输出共一行，即最少按键次数,若无法到达，则输出 −1 。

输入样例:

  1. 5 1 5
  2. 3 3 1 2 5

输出样例:

3

这道题也是典型bfs的题目，具体的实现即解释也在代码中

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. int judge(int arr[])
  5. {
  6.     int i=0;
  7.     for(i=0;i<2000;i++)
  8.     {
  9.         if(arr[i]!=0)
  10.             return 1;
  11.     }
  12.     return 0;
  13. }
  14. int main()
  15. {
  16.     int n;
  17.     scanf("%d",&n);
  18.     int arr[n+1];
  19.     int i=0;
  20.     int sta,end;
  21.     scanf("%d%d",&sta,&end);
  22.     for(i=1;i<=n;i++)
  23.     {
  24.         scanf("%d",&arr[i]);
  25.     }
  26.     arr[0]=0;
  27.     int queque[2000];//模拟队列的实现
  28.     memset(queque,0,sizeof(queque));
  29.     int top=0,bottom=1;
  30.     queque[top]=sta;
  31.     int count=0;
  32.     int flag=0;
  33.     while(judge(queque))
  34.     {
  35.         //广搜对一层的搜索
  36.         int tmp=bottom;
  37.         while(top<tmp)
  38.         {
  39.            //此处节点标记采用arr[i]=0方式
  40.             if(arr[queque[top]]!=0)
  41.             {
  42.                if(queque[top]+arr[queque[top]]<=n)
  43.                {
  44.                 //对上楼层节点进行访问，将可访问节点放入队列并标记该节点
  45.                 queque[bottom++]=queque[top]+arr[queque[top]];
  46.                 //arr[queque[top]+arr[queque[top]]]=0;
  47.                }
  48.                if(queque[top]-arr[queque[top]]>0)
  49.                {
  50.                 //对下楼层进行访问，将可访问节点放入队列并标记该节点
  51.                 queque[bottom++]=queque[top]-arr[queque[top]];
  52.                }
  53.                 arr[queque[top]]=0;
  54.             }
  55.             top++;
  56.         }
  57.         //搜索一次就需要按一次电梯
  58.         count++;
  59.         //判断目前的层数中有无目标数
  60.         int i=0;
  61.         for(;i<top;i++)
  62.         {
  63.             if(queque[i]==end)
  64.             {
  65.                 flag=1;
  66.                  goto ending;
  67.             }
  68.             queque[i]=0;
  69.         }
  70.     }
  71.     ending:
  72.     if(flag)
  73.     printf("%d",count-1);
  74.     else
  75.     printf("-1");
  76.     return 0;
  77. }

2，寻宝 

奕哥今天玩到一款寻宝游戏，地图是一个n*m的矩阵，其中分布着一些宝藏，每个宝藏具有一定的价值，奕哥只能拿走其中一个宝藏。奕哥起始在a行b列。奕哥可以向相邻的一格移动，但不能走出地图外。奕哥初始体力值X，移动一格需要消耗体力值为1。体力耗尽后奕哥无法继续移动。地图中有一些障碍物，奕哥无法移动到障碍物上。奕哥想知道他能拿到的最具价值的宝藏是哪一个。

输入格式:

第一行包含5个整数n,m,a,b,X。n,m分别表示地图行数，列数；a,b表示奕哥起始位置在a行b列；X表示奕哥的体力。

（ 1<=n,m<=1000, 1<=a<=n, 1<=b<=m, 0<=X<=1e10）

接下来n行，每行m个整数。第i行第j个整数为Aij （-1<=Aij<=1e9）。若Aij=-1,则表示第i行第j列有障碍物；否则表示该位置有一个价值为Aij的宝物。保证起始位置没有障碍物。

输出格式:

奕哥能拿到价值最高的宝藏的价值。

输入样例:

  1. 3 3 1 1 3
  2. 0 -1 10
  3. 3 5 7
  4. -1 8 15

输出样例：

8

这就是迷宫题了，上面的点已经说得清楚了，不懂的可以再上去看看

  1. #include<stdio.h>
  2. #include<string.h>
  3. int local[][2]=
  4. {
  5.     {0,1},
  6.     {0,-1},
  7.     {1,0},
  8.     {-1,0}
  9. };
  10. struct node
  11. {
  12.     int num;
  13.     int i;
  14.     int j;
  15. };
  16. int main()
  17. {
  18. 	int n, m, a, b, x;
  19. 	scanf("%d%d%d%d%d", &n, &m, &a, &b, &x);
  20. 	a--;//数组中初始位置要减一
  21. 	b--;
  22. 	int arr[n][m];//读入地图
  23.     int i=0;
  24. 	for (i = 0; i<n; i++)
  25. 	{
  26. 		int j = 0;
  27. 		for (j = 0; j<m; j++)
  28. 		{
  29. 			scanf("%d", &arr[i][j]);
  30. 		}
  31. 	}
  32.     struct node queque[10000];
  33.     memset(queque,0,sizeof(queque));
  34.     int head=0,end=1;
  35.     queque[head].num=arr[a][b];
  36.     queque[head].i=a;//记录对应数值的坐标
  37.     queque[head].j=b;
  38.     arr[a][b]=-1;//搜索过的就直接标记
  39.     while(x--)
  40.     {
  41.         int tmp=end;
  42.         while(head<tmp)//一层搜索
  43.         {
  44.            for(int i=0;i<4;i++)//每个点搜索四个方位
  45.            {
  46.                int tmpi=queque[head].i+local[i][0];
  47.                int tmpj=queque[head].j+local[i][1];
  48.                if(tmpi<0||tmpi>=n||tmpj<0||tmpj>=m)//判断边界条件
  49.                {
  50.                    continue;
  51.                }
  52.                else if(arr[tmpi][tmpj]==-1)//搜索过的或者不可走点
  53.                {
  54.                    continue;
  55.                }
  56.                else
  57.                {
  58.                    //存下数值和地址，并将其入队
  59.                    queque[end].num=arr[tmpi][tmpj];
  60.                    queque[end].i=tmpi;
  61.                    queque[end].j=tmpj;
  62.                    end++;
  63.                    arr[tmpi][tmpj]=-1;
  64.                }
  65.            }
  66.             head++;
  67.         }
  68.     }
  69.     int max=0;
  70.     for(int i=0;i<end;i++)
  71.     {
  72.         if(queque[i].num>max)
  73.             max=queque[i].num;
  74.     }
  75.     printf("%d",max);
  76. 	return 0;
  77. }

3，龙舌兰酒吧 

有一个大小为n*m的矩形小镇，城镇上有房屋（“#”表示无法通过），有空地（“.”表示可通行），每次移动只能朝上下左右四个方向，且需花费1单位时间。

一天，二乔和承太郎约定在龙舌兰酒吧见面，两人同时从各自所在位置向酒吧出发。请问最少需要过多少时间他们才能在酒吧碰面。

地图上P表示二乔的位置，W表示承太郎的位置，B表示酒吧的位置。

输入格式:

第一行包含两个整数n,m，表示城镇的大小。（1<=m,n<=1000)。

接下来n行，每行m个字符，表示小镇的情况。

输出格式:

输出两人在酒吧碰面的最少花费时间，如果无法在酒吧碰面则输出-1。

输入样例:

  1. 5 4
  2. .W.#
  3. P#..
  4. ....
  5. B..#
  6. #...

输出样例:

4

具体代码实现如下：

  1. #include<stdio.h>
  2. #include<string.h>
  3. //四个方位
  4. int local[][2]={
  5.     {0,1},
  6.     {0,-1},
  7.     {1,0},
  8.     {-1,0}
  9. };
  10. struct node
  11. {
  12.     char ch;
  13.     int i;
  14.     int j;
  15. };
  16. int judge(struct node *queque,int n)
  17. {
  18.     int i=0;
  19.     for(;i<n;i++)
  20.     {
  21.         if(queque[i].ch!=0)
  22.             return 1;
  23.     }
  24.     return 0;
  25. }
  26. int main()
  27. {
  28.     int n,m;
  29.     scanf("%d%d",&n,&m);
  30.     char arrp[n][m];//供p寻找
  31.     char arrw[n][m];//供w寻找
  32.     struct node queque[600000];//模拟队列实现
  33.     memset(queque,0,sizeof(queque));
  34.     for(int i=0;i<n;i++)
  35.     {
  36.         getchar();
  37.         for(int j=0;j<m;j++)
  38.         {
  39.             scanf("%c",&arrp[i][j]);
  40.         }
  41.     }
  42.     for(int i=0;i<n;i++)
  43.     {
  44.         for(int j=0;j<m;j++)
  45.             arrw[i][j]=arrp[i][j];
  46.     }
  47.     int pi,pj,wi,wj,tari,tarj;
  48.     for(int i=0;i<n;i++)
  49.     {
  50.         for(int j=0;j<m;j++)
  51.         {
  52.             if(arrp[i][j]=='P')//找到P坐标
  53.             {
  54.                 pi=i;
  55.                 pj=j;
  56.             }
  57.             if(arrp[i][j]=='W')//找到W坐标
  58.             {
  59.                 wi=i;
  60.                 wj=j;
  61.             }
  62.         }
  63.     }
  64.     
  65.   /*
  66.   此处为测试arrp和arrw是否正常 
  67.          for(int i=0;i<n;i++)
  68.     {
  69.         for(int j=0;j<m;j++)
  70.         {
  71.             printf("%c",arrw[i][j]);
  72.         }
  73.         printf("\n");
  74.     }
  75.    */
  76.     int countp=0;
  77.     int countw=0;
  78.     int flag1=0;
  79.     //此处开始为两次bfs的实现
  80.     //1.arrp的路径寻找
  81.     int head=0;
  82.     int end=1;
  83.     queque[head].ch=arrp[pi][pj];
  84.     queque[head].i=pi;
  85.     queque[head].j=pj;
  86.     while(judge(queque,end))//判断队列是否为空
  87.     {
  88.         int tmp=end;
  89.         while(head<tmp)
  90.         {
  91.           for(int i=0;i<4;i++)
  92.           {
  93.               int tmpi=queque[head].i+local[i][0];
  94.               int tmpj=queque[head].j+local[i][1];
  95.               if(tmpi<0||tmpi>=n||tmpj<0||tmpj>=m)
  96.                   continue;
  97.               else if(arrp[tmpi][tmpj]=='#')
  98.                   continue;
  99.               else
  100.               {
  101.                   queque[end].ch=arrp[tmpi][tmpj];
  102.                   queque[end].i=tmpi;
  103.                   queque[end].j=tmpj;
  104.                   arrp[tmpi][tmpj]='#';
  105.                   end++;
  106.               }
  107.           }
  108.             queque[head].ch=0;//搜索完出队列
  109.             head++;
  110.         }
  111.         countp++;//搜索完一次走一步
  112.         for(int i=head;i<end;i++)
  113.         {
  114.             if(queque[i].ch=='B')
  115.             {
  116.                 flag1=1;
  117.                 break;
  118.             }
  119.         }
  120.         if(flag1)
  121.             break;
  122.     }
  123.     memset(queque,0,sizeof(queque));
  124.     head=0;
  125.     end=1;
  126.     queque[head].ch=arrw[wi][wj];
  127.     queque[head].i=wi;
  128.     queque[head].j=wj;
  129.     //2.arrw路径寻找
  130.     int flag2=0;
  131.     while(judge(queque,end))//判断队列是否为空
  132.     {
  133.         int tmp=end;
  134.         while(head<tmp)
  135.         {
  136.           for(int i=0;i<4;i++)
  137.           {
  138.               int tmpi=queque[head].i+local[i][0];
  139.               int tmpj=queque[head].j+local[i][1];
  140.               if(tmpi<0||tmpi>=n||tmpj<0||tmpj>=m)
  141.                   continue;
  142.               else if(arrw[tmpi][tmpj]=='#')
  143.                   continue;
  144.               else
  145.               {
  146.                   queque[end].ch=arrw[tmpi][tmpj];
  147.                   queque[end].i=tmpi;
  148.                   queque[end].j=tmpj;
  149.                   arrw[tmpi][tmpj]='#';
  150.                   end++;
  151.               }
  152.           }
  153.             queque[head].ch=0;
  154.             head++;
  155.         }
  156.         countw++;
  157.         for(int i=head;i<end;i++)
  158.         {
  159.             if(queque[i].ch=='B')
  160.             {
  161.                 flag2=1;
  162.                 break;
  163.             }
  164.         }
  165.         if(flag2)
  166.             break;
  167.     }
  168.     if(flag1==0||flag2==0)
  169.         printf("-1");
  170.     else
  171.     {
  172.         printf("%d",countp>countw?countp:countw);
  173.     }
  174.     return 0;
  175. }

四，总结 

总体来说，bfs理解了就会很难（doge），bfs也是图论的一个基础算法，希望这篇文章能帮助到你掌握bfs，看到这里不妨给我点个赞吧。之后大概就是一周一篇了。要多输入，才能有输出嘛，多数时间还是要拿来学习的。（还是太菜）。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/445370
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号