福州夏令营第二天

本文主要是介绍福州夏令营第二天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天已经是第二天了，今天我们学习了BFS，说是学习，不如说是复习吧，但也收获了很多。除了BFS外，我们还学了一些深度优先搜索的剪枝，这真的是一样非常玄学的东西。讲了一些的题目，有一些题目非常的简单，我以前的基础是可以完全理解并解决的。但同时，我们也讲了一些难题，这一些题目当时讲得时候我可能有一些茫然，所以课后，就不得不去自己思考一下了。

先讲一道BFS的题目吧，这是我们的老师先抬出来的，可以说是学BFS的基础题吧。

骑士救公主（题目忘了，救勉强来凑合一下吧）

题目描述大概就是一个骑士（R）要在一个n*m的方格中移动到公主的位置（A），每一次移动都需要花费1的时间，这个方格内还有非常多的不能通过的墙（#），普通的道路（.）。同时，一路上还有非常多的守卫（R），骑士移动到守卫的位置必须打败守卫，但需要消耗1的时间。求最短的时间。如果无法到达，就输出NO。

冷静分析：

竟然是找最短的，那么求的一定是最优解。我们的BFS正是用来求最优解的大宝贝。但是如果用DFS一条路走到黑的话，时间复杂度太高，会用大把的时间来走错误的路，最后的结果也就可想而知（嘿嘿嘿）。知道了算法，那就好办了。

老师给我们讲了一遍，不过我觉得老师讲得很清晰，但是我还是想要用自己的方法：我们可以把整个方格用int类型存储起来，如果是墙的话，就记为0，如果是骑士，普通的路或者公主的话，就记为1，如果是守卫的话，就记为2。每次通过时，如果当前的值>=1，就说明不是墙，那么就把当前的值加起来。当然，我们先要初始化一下，把四周的不能走的地方记为0。

代码如下：

#include<bits/stdc++.h>
using namespace std;int n,m,k,a[200][200]={0,0},vis[20000]={0},x[1000]={0},y[1000]={0},xx,yy,dx[5]={1,-1,0,0},dy[5]={0,0,1,-1};
char b[200][200]={};void bfs()
{int tail=1,head=1;while(tail>=head){for(int i=0;i<=3;i++){int xxx=x[head]+dx[i],yyy=y[head]+dy[i];if(a[xxx][yyy]>=1){tail++;vis[tail]=vis[head]+a[xxx][yyy];a[xxx][yyy]=0;x[tail]=xxx;y[tail]=yyy;}if(xxx==xx&&yyy==yy){cout<<vis[tail];return;}}head++;}cout<<"NO";
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>b[i][j];if(b[i][j]=='.')a[i][j]=1;else if(b[i][j]=='R')a[i][j]=1,x[1]=i,y[1]=j;else if(b[i][j]=='A')a[i][j]=1,xx=i,yy=j;else if(b[i][j]=='S')a[i][j]=2;}bfs();return 0;
}

注释就不加了，老师说加注释很麻烦的。。。

这样就可以过了。

另外，我们也要来一道深搜的剪枝。就举老师讲得小木棍吧。（~~欢迎来到乱七八糟忘记题面，所有题目全靠乱编~~）