搜索算法
广度优先搜索 BFS
BFS主要求解两种问题：
- 最短距离：给出一个起始点，一个终点，并求出在地图上从起点到终点的最短距离
- 最小步数：从一种状态变换到另一种状态的最小步数
总的来说BFS求的是最小问题，是基于迭代的，相对于DFS来说不会爆栈，因此在BFS和DFS同时可用时，优先使用BFS。
BFS有一种性质：当所有边的权重都相等时，从起点开始搜索，可以得到所有点的最短距离【因为BFS可能会有多条路径，但每一条路径都同时走一步，所以先到达某点的路径就是最短路径】
Flood Fill算法
顾名思义，Flood Fill算法即洪水填充算法，给出一个起始点，填充附近的点。
Flood Fill算法可以在线性时间复杂度内找到某个点所在的连通块【连通块就是根据连通规则所递归连通的连通块】。
Flood Fill 算法也就是BFS的其中一种算法，给出一个点，然后使用一个队列，将连通点加入队列，然后再一直加入，直到队列空。
八连通与四连通
八连通就是一个点与附近的八个点是连通的，四连通就是一个点与其上、下、左、右四个点是连通的，除了这两种，还有日字连通，就是一个点与可以组成 “日” 字的对角线点是连通的。因为要递归访问连通点，因此需要遍历连通点，以下是遍历方式：
// 表示坐标的方便方法
#define x first
#define y second
typedef pair<int,int> PII;
// 八连通 p为点，p.x p.y 分别为p的x坐标与y坐标
for(int i=p.x-1;i<p.x+1;++i){
for(int j=p.y-1;j<p.y+1;++j){
PII new_p={i,j};
//操作
}
}
// 四连通，因为只有四个点，就可以使用数组存储坐标来进行遍历
int dx[]={0,-1,0,1}，dy[]={-1,0,1,0}; //存储相对于p.x的差值
for(int i=0;i<4;++i){
PII new_p={p.x+dx[i],p.y+dy[j]};
//操作
}
// 日字连通，与四连通类似方法
int dx[]={-2,-1,1,2,2,1,-1,-2};
int dy[]={1,2,2,1,-1,-2,-2,-1};
for(int i=0;i<8;++i){
PII new_p={p.x+dx[i],p.y+dy[i]};
//操作
}
城堡问题
题目描述
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(图 1)
# = Wall
| = No wall
- = No wall
方向：上北下南左西右东。
图1是一个城堡的地形图。
请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。
城堡被分割成 m∗n (m<=50, n<=50)个方格区域，每个方格区域可以有0~4面墙。
注意：墙体厚度忽略不计。
输入格式
第一行包含两个整数 m 和 n，分别表示城堡南北方向的长度和东西方向的长度。
接下来 m 行，每行包含 n 个整数，每个整数都表示平面图对应位置的方块的墙的特征。
每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。
例如，如果一个方块的 P 为3，则 3 = 1 + 2，该方块包含西墙和北墙。
城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。
输入的数据保证城堡至少有两个房间。
输出格式
共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。
样例
输入样例：
4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
输出样例：
5
9
题解
这题就是计算有多少个连通块，并把最大的连通块面积输出。因此，此题使用Flood Fill算法，但难点就是表示墙的方式，使用一个数来代表南、东、北、西，依据题意分别是8、4、2、1，很像二进制的四位数，比如0110=6就是东北有墙，这样的话就可以采用与1，分别将数字右移0、1、2、3位然后与1，这样就可以知道西、北、东、南是否有墙。除此之外，若是先知道某个点的非墙位置然后再入队列，那么这样就会增加代码复杂度，可以先遍历点的四连通点，然后再判断两者之间是否有墙进而入队列。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=55,M=N*N;
int m,n;
int g[N][N]; //地图
PII q[M]; //伪队列
bool st[N][N]; //点状态
int bfs(int sx,int sy){
int dx[]={0,-1,0,1},dy[]={-1,0,1,0}; //注意是数组坐标，dx是竖坐标
int hh=0,tt=0; //队首与队尾
int area=0;
q[0]={sx,sy}; //加入队列
st[sx][sy]=true; //更新状态
while(hh<=tt){
PII t=q[hh++]; //队首坐标
area++;
for(int i=0;i<4;++i){
int a=t.x+dx[i],b=t.y+dy[i];
if(a<0 || a>=m || b<0 || b>=n)continue; //边界条件
if(st[a][b])continue; //被访问过
if(g[t.x][t.y] >> i & 1)continue; //两者之间有墙
q[++tt]={a,b}; //入队
st[a][b]=true; //更新状态
}
}
return area;
}
int main(){
cin >> m >> n;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
cin >> g[i][j];
}
}
int cnt=0,area=0;
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(!st[i][j]){
//遍历图上所有点，当此点未被遍历过时，bfs
cnt++;
area=max(area,bfs(i,j));
}
}
}
cout << cnt << endl << area;
return 0;
}
最短路模型
迷宫问题
描述
定义一个二维数组：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
输入
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径，格式如样例所示。
样例输入
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
样例输出
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
题解
虽然BFS可以找出最短距离，但却无法记录是哪一条路径，因为BFS的特性，不同路径一定不会交叉只会分叉（因为交叉了说明有条路径提前到达，那么这条路径就可以结束了，因为不可能会比提前到的更快），因此可以使用一个pari类型的二维数组，二维代表原坐标，而值就是走到此点的上一坐标。这样就可以当搜索到终点时，从终点退回输出即可。【可能你会想到根当权重不同时，也可以使用int类型的二维数组记录到达此点距离，当搜索到终点时，就可以找出最短距离，这是不对的，因为当交叉的时候，不知提前到的路径短还是后到的路径短，也许可以先比较，若更短则更新否则不更新】
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 5,M=N*N;
int n=N;
int g[N][N];
PII q[M];
PII pre[N][N];
void bfs(int sx,int sy){
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int hh=0,tt=0;
q[0]={sx,sy};
memset(pre,-1,sizeof pre);
pre[sx][sy]={0,0};
while(hh<=tt){
PII t=q[hh++];
for(int i=0;i<4;++i){
int a=t.x+dx[i],b=t.y+dy[i];
if(a<0 || a>=n || b<0 || b>=n)continue;
if(g[a][b])continue;
if(pre[a][b].x!=-1)continue;
q[++tt]={a,b};
pre[a][b]=t;
}
}
}
int main(){
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cin >> g[i][j];
}
}
bfs(4,4); //从终点到起点，再从起点回退
PII end={0,0};
while(true){
printf("(%d, %d)\n",end.x,end.y);
if(end.x==n-1 && end.y==n-1)break;
end=pre[end.x][end.y];
}
return 0;
}
抓住那头牛
描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入
两个整数，N和K
输出
一个整数，农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
题解
这题也是BFS，这种类型是有多种方式达到下一点，而走完一步后依旧有那么多的方式继续走，而每一种方式的权重都相同，但所到达的点不同，这样就可以用BFS，因为BFS可以分出多条路径，而每一条路径同时走相同的步数，这样最先到达终点的路径就是最短路径。但这题需要计算花费的时间，虽然每条路径都同时走一步，但不确定到底是哪一步往前走了，所以无法使用一个变量来计算时间。可以使用一个int类型的二维数组记录走到当前所消耗的时间。【因为不可能同时走到同一点，因此不用考虑覆盖问题】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=2e5+10; //注意范围，可能会到两倍的10000
int n,k;
int q[N];
int dist[N];
int bfs(){
memset(dist,-1,sizeof dist);
dist[n]=0;
q[0]=n;
int hh=0,tt=0;
while(hh<=tt){
int t=q[hh++];
if(t==k) return dist[k];
if(t+1>=0&&dist[t+1]==-1){
q[++tt]=t+1;
dist[t+1]=dist[t]+1;
}
if(t-1>=0&&dist[t-1]==-1){
q[++tt]=t-1;
dist[t-1]=dist[t]+1;
}
if(t*2>=0&&dist[t*2]==-1){
q[++tt]=t*2;
dist[t*2]=dist[t]+1;
}
}
return -1;
}
int main(){
cin >> n >> k;
cout << bfs() << endl;
return 0;
}
