（c语言实现）算法笔记之bfs及pta习题

目录

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

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

三，题型训练

1，奇怪的电梯

2，寻宝 

3，龙舌兰酒吧 

四，总结 

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的应用在于寻找最短路径类，之后如果有遇到其他的应用，会再写一篇文章来描述新的应用。

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

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

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         {
           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++;
        }

 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 。

输入样例:

5 1 5
3 3 1 2 5

输出样例:

3

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

#include
#include
#include
int judge(int arr[])
{
    int i=0;
    for(i=0;i<2000;i++)
    {
        if(arr[i]!=0)
            return 1;
    }
    return 0;
}
int main()
{
    int n;
    scanf("%d",&n);
    int arr[n+1];
    int i=0;
    int sta,end;
    scanf("%d%d",&sta,&end);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
    }
    arr[0]=0;
    int queque[2000];//模拟队列的实现
    memset(queque,0,sizeof(queque));
    int top=0,bottom=1;
    queque[top]=sta;
    int count=0;
    int flag=0;
    while(judge(queque))
    {
        //广搜对一层的搜索
        int tmp=bottom;
        while(top0)
               {
                //对下楼层进行访问，将可访问节点放入队列并标记该节点
                queque[bottom++]=queque[top]-arr[queque[top]];
               }
                arr[queque[top]]=0;
            }
            top++;
        }
        //搜索一次就需要按一次电梯
        count++;
        //判断目前的层数中有无目标数
        int i=0;
        for(;i

#include
#include
int local[][2]=
{
    {0,1},
    {0,-1},
    {1,0},
    {-1,0}
};
struct node
{
    int num;
    int i;
    int j;
};
int main()
{
	int n, m, a, b, x;
	scanf("%d%d%d%d%d", &n, &m, &a, &b, &x);
	a--;//数组中初始位置要减一
	b--;
	int arr[n][m];//读入地图
    int i=0;
	for (i = 0; i=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++;
        }
    }
    int max=0;
    for(int i=0;imax)
            max=queque[i].num;
    }
    printf("%d",max);
	return 0;
}

#include
#include
//四个方位
int local[][2]={
    {0,1},
    {0,-1},
    {1,0},
    {-1,0}
};
struct node
{
    char ch;
    int i;
    int j;
};
int judge(struct node *queque,int n)
{
    int i=0;
    for(;i=n||tmpj<0||tmpj>=m)
                  continue;
              else if(arrp[tmpi][tmpj]=='#')
                  continue;
              else
              {
                  queque[end].ch=arrp[tmpi][tmpj];
                  queque[end].i=tmpi;
                  queque[end].j=tmpj;
                  arrp[tmpi][tmpj]='#';
                  end++;
              }
          }
            queque[head].ch=0;//搜索完出队列
            head++;
        }
        countp++;//搜索完一次走一步
        for(int i=head;i=n||tmpj<0||tmpj>=m)
                  continue;
              else if(arrw[tmpi][tmpj]=='#')
                  continue;
              else
              {
                  queque[end].ch=arrw[tmpi][tmpj];
                  queque[end].i=tmpi;
                  queque[end].j=tmpj;
                  arrw[tmpi][tmpj]='#';
                  end++;
              }
          }
            queque[head].ch=0;
            head++;
        }
        countw++;
        for(int i=head;icountw?countp:countw);
    }
    return 0;
}