BFS
1、小X学游泳
【题解】枚举每一个点作为连通块的起点，求得连通块大小，然后打擂台求最值即可。
【参考代码】
#include <iostream>
#include <iomanip>
#include <queue>
#include <algorithm>
using namespace std;
char ch[105][105];
int n,m,MAXX;
int d[4][2]={-1,0,0,1,1,0,0,-1};//上、右、下、左4个方向位移量
struct node // 存放每个位置的行列坐标
{
int x;
int y;
};
int bfs(int x,int y)
{
queue<node> Q;
int sum=1; // 初始为1（包含起始位置）
const char c=ch[x][y];//保存水深数据
ch[x][y]='0'; // 改变状态
Q.push((node){x,y}); // 将起始位置信息入队
while(!Q.empty()) // 队非空
{
for(int i=0;i<4;i++) // 搜索上右下左
{
int dx=Q.front().x+d[i][0];//当前行
int dy=Q.front().y+d[i][1];//当前列
if(dx>=0 && dx<n && dy>=0 && dy<m && ch[dx][dy]==c) // 未越界，水深相同
{
sum++;// 面积加1
ch[dx][dy]='0';//标记状态
Q.push((node){dx,dy});// 入队
}
}
Q.pop();//队头出队
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>ch[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(ch[i][j]!='0')
{
MAXX=max(MAXX,bfs(i,j)); //调用bfs，打擂台求出每片区域的最大值
}
}
}
cout<<MAXX<<endl;// 完美输出 OK
return 0;
}
2、迷宫出口
【题解】我们曾经用深搜（DFS）的方式写过该题目；我们暴力枚举要走的每一步，以点的坐标作为枚举对象进行枚举即可。
【参考代码】
#include <iostream>
#include <iomanip>
#include <queue>
#include <algorithm>
using namespace std;
int a[105][105];
int n,sx,sy,ex,ey;
int d[4][2]={-1,0,0,1,1,0,0,-1};//上、右、下、左4个方向位移量
struct node // 存放每个位置的行列坐标
{
int x;
int y;
};
void bfs(int x,int y)
{
queue<node> Q;
a[x][y]=1; // 改变状态
Q.push((node){x,y}); // 将起始位置信息入队
while(!Q.empty()) // 队非空
{
for(int i=0;i<4;i++) // 搜索上右下左
{
int dx=Q.front().x+d[i][0];//当前行
int dy=Q.front().y+d[i][1];//当前列
if(dx>=1 && dx<=n && dy>=1 && dy<=n && a[dx][dy]==0)// 未越界，能走
{
a[dx][dy]=1;//标记状态
Q.push((node){dx,dy});// 入队
if(dx==ex && dy==ey) // 哇，哇，到了耶！
{
cout<<"YES"<<endl; // 输出
return ; //结束
}
}
}
Q.pop();//队头出队
}
cout<<"NO"<<endl; // 好难受，无法到达啊
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
cin>>sx>>sy>>ex>>ey;
if(a[sx][sy]==1) //若起点就无法通行
{
cout<<"NO"<<endl; // 输出NO
return 0; // 直接结束吧 ，别搜了
}
bfs(sx,sy);
return 0;
}
3、走出迷宫的最少步数
【题解】此类问题使用DFS、BFS都可以达到目标。但要注意二者的区别，首先就时间复杂度而言DFS更耗费时间；就搜索顺序而言，虽然二者的搜索解答树是一样的，但是DFS是按照顺序枚举的，可以很容易得到字典序最小的答案序列；而BFS则不是。
【参考代码】
#include <iostream>
#include <iomanip>
#include <queue>
#include <algorithm>
using namespace std;
char ch[50][50];
int n,m;
int d[4][2]={-1,0,0,1,1,0,0,-1};//上、右、下、左4个方向位移量
struct node // 存放每个位置的行列坐标 步数
{
int x;
int y;
int step;//步数
};
void bfs(int x,int y)
{
queue<node> Q;
ch[x][y]='#'; // 改变状态
Q.push((node){x,y,1}); // 将起始位置信息入队
while(!Q.empty()) // 队非空
{
for(int i=0;i<4;i++) // 搜索上右下左
{
int dx=Q.front().x+d[i][0];//当前行
int dy=Q.front().y+d[i][1];//当前列
if(dx>=1 && dx<=n && dy>=1 && dy<=m && ch[dx][dy]!='#')// 未越界，不是障碍物
{
ch[dx][dy]='#';//标记状态
Q.push((node){dx,dy,Q.front().step+1});// 入队
if(dx==n && dy==m) // 到达右下角
{
cout<<Q.front().step+1<<endl; // 输出步数
return ; //结束
}
}
}
Q.pop();//队头出队
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ch[i][j];
}
}
bfs(1,1);//从左上角开始
return 0;
}
4、走出迷宫的最少步数2
【题解】与上一题异曲同工，建议自己独立写完整代码
【参考代码】
#include <iostream>
#include <iomanip>
#include <queue>
#include <algorithm>
using namespace std;
char ch[105][105];
int n,m,sx,sy,ex,ey;
int d[4][2]={-1,0,0,1,1,0,0,-1};//上、右、下、左4个方向位移量
struct node // 存放每个位置的行列坐标 步数
{
int x;
int y;
int step;//步数
};
void bfs(int x,int y)
{
queue<node> Q;
ch[x][y]='#'; // 改变状态
Q.push((node){x,y,0}); // 将起始位置信息入队
while(!Q.empty()) // 队非空
{
for(int i=0;i<4;i++) // 搜索上右下左
{
int dx=Q.front().x+d[i][0];//当前行
int dy=Q.front().y+d[i][1];//当前列
if(dx>=1 && dx<=n && dy>=1 && dy<=m && ch[dx][dy]!='#')// 未越界，不是障碍物
{
ch[dx][dy]='#';//标记状态
Q.push((node){dx,dy,Q.front().step+1});// 入队
if(dx==ex && dy==ey) // 到达终点
{
cout<<Q.front().step+1<<endl; // 输出步数
return ; //结束
}
}
}
Q.pop();//队头出队
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ch[i][j];
if(ch[i][j]=='S') // 记录起点位置
{
sx=i;
sy=j;
}
if(ch[i][j]=='T')//记录终点位置
{
ex=i;
ey=j;
}
}
}
bfs(sx,sy);//从起点开始bfs
return 0;
}
5、数池塘
【视频讲解】
6、骑士巡游
【题解】该题目与马的遍历非常接近，注意八个方向的方向数组的构造
【参考代码】
#include <bits/stdc++.h>
using namespace std;
int a[15][15];
int d[8][2]={-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2};
struct node
{
int x;
int y;
int step;
};
int n,m,sx,sy,ex,ey;
void bfs(int x,int y)
{
queue<node> Q;
Q.push((node){x,y,0});
while(!Q.empty())
{
for(int i=0;i<8;i++) // 马的8个方向
{
int dx=Q.front().x+d[i][0];//新的行
int dy=Q.front().y+d[i][1];//新的列
int s=Q.front().step+1;//当前步数
if(dx>=1 && dx<=n && dy>=1 && dy<=m && a[dx][dy]==0)// 未越界，能走
{
a[dx][dy]=1;// 改变当前点的状态
Q.push((node){dx,dy,s});//入队
if(dx==ex && dy==ey) //判断，到达目标点
{
cout<<s<<endl;// 输出步数
return ;
}
}
}
Q.pop();
}
}
int main()
{
cin>>n>>m>>sx>>sy>>ex>>ey;
a[sx][sy]=1;// 改变起点状态，以便后面不被搜到
bfs(sx,sy);// 从起点位置展开bfs
return 0;
}
7、骑士牛
【视频讲解】
8、走出迷宫的最短路径
【题解】此题与迷宫问题一样的，但是最后需要输出路径，所以重点关注路径输出是如何解决的。
【参考代码】
#include <bits/stdc++.h>
using namespace std;
int a[160][160];
int p[160][160][2];// 用于保存来自上一步的行、列号
int d[4][2]={-1,0,0,1,1,0,0,-1};
struct node
{
int x;
int y;
};
int n,m,sx,sy,ex,ey;
void print(int x,int y)
{
if(x==0 && y==0) return ;//递归边界
print(p[x][y][0],p[x][y][1]);//递归上一个：我来自哪里？？？
cout<<"("<<x<<","<<y<<")"<<"->"; // 利用栈的特性依次输出
}
void bfs(int x,int y)
{
queue<node> Q;
Q.push((node){x,y});//将出发地信息入队
while(!Q.empty())
{
for(int i=0;i<4;i++) // 4个方向bfs
{
int dx=Q.front().x+d[i][0];//新的行
int dy=Q.front().y+d[i][1];//新的列
if(dx>=1 && dx<=n && dy>=1 && dy<=m && a[dx][dy]!=1)// 未越界，能通行
{
p[dx][dy][0]=Q.front().x;//记录保存来自的行
p[dx][dy][1]=Q.front().y; //记录保存来自的列
a[dx][dy]=1;// 改变当前点的状态
Q.push((node){dx,dy});//将到达的当前位置信息入队
if(dx==ex && dy==ey)//判断，到达目标点
{
print(p[dx][dy][0],p[dx][dy][1]); // 调用递归输出函数
cout<<"("<<dx<<","<<dy<<")"<<endl;//最后再输出终点坐标
return ;
}
}
}
Q.pop();
}
cout<<"no way"<<endl; // 哇，累死我了，怎么也走不到终点，输出no way
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
cin>>sx>>sy;
cin>>ex>>ey;
p[sx][sy][0]=p[sx][sy][1]=0;//将起始位置的初始值记为0
a[sx][sy]=1;//标记，将出发地标记为不能通行
bfs(sx,sy);//从起始位置展开bfs
return 0;
}
9、泉水
【视频讲解】
10、最小拐弯路径
【题解】广搜，使用while循环从队列的头部对应的点一直向一个方向走，如果该点能走，判断该点不在队列中，则入队；第一次走到终点时，对应的弯道次数，就是最小弯道次数；
【视频讲解】
DFS
1、卒的遍历
【题解】该题是DFS的模板题，但要注意二点的处理。一是先下后右，可以通过方向数组定义来解决；二是路径输出的处理，此处采用的递归方式输出；
【参考代码】
#include <bits/stdc++.h>
#define P pair<int,int>
using namespace std;
int a[10][10],p[10][10][2];
bool vis[10][10];
int n,m,sum;
int d[2][2]={1,0,0,1};
void print(int x,int y)
{
if(x==0 && y==0) return ;
print(p[x][y][0],p[x][y][1]);
cout<<x<<","<<y<<"->";
}
void dfs(int x,int y)
{
if(x==n && y==m) // 边界 到达终点
{
sum++;//方案计数
cout<<sum<<":"; //当前方案
print(p[n][m][0],p[n][m][1]); //递归输出方案
cout<<n<<","<<m<<endl;
return ;
}
for(int i=0;i<2;i++) //下 右 2个方向
{
int dx=x+d[i][0];//当前行
int dy=y+d[i][1];//当前列
if(dx>=1 && dx<=n && dy>=1 && dy<=m && !vis[dx][dy]) //合法，且未访问过
{
p[dx][dy][0]=x;//保存来自行
p[dx][dy][1]=y;//保存来自列
vis[dx][dy]=true;//标记为已访问
dfs(dx,dy); //从当前位置继续一路搜下去
vis[dx][dy]=false;//回溯
}
}
}
int main() {
cin>>n>>m;
p[1][1][0]=p[1][1][1]=0;//初始为0（递归边界）
dfs(1,1);
return 0;
}
2、马的遍历
【题解】关注输出方式的不同。
【参考代码1】
#include <bits/stdc++.h>
using namespace std;
bool vis[10][10];
int a[10][10][2];
int d[4][2]={2,1,1,2,-1,2,-2,1}; //4个方向位移量
int sum;
void print(int x,int y)
{
if(x==0 && y==0)
{
cout<<0<<","<<0<<"->";
return ;
}
print(a[x][y][0],a[x][y][1]);
cout<<x<<","<<y<<"->";
}
void dfs(int x,int y)
{
if(x==4 && y==8) //边界（到达终点）
{
sum++;//方案计数
cout<<sum<<":";//输出当前方案数
print(a[x][y][0],a[x][y][1]); //递归输出
cout<<x<<","<<y<<endl; //最后再输出终点坐标
return ;
}
for(int i=0;i<4;i++)
{
int dx=x+d[i][0];//当前行
int dy=y+d[i][1];//当前列
if(dx>=0 && dx<=4 && dy>=0 && dy<=8 && !vis[dx][dy])//合法 没来过
{
vis[dx][dy]=true;//标记
a[dx][dy][0]=x;//记录来自的行
a[dx][dy][1]=y;//记录来自的列
dfs(dx,dy);//继续走
vis[dx][dy]=false;//回溯
}
}
}
int main() {
vis[0][0]=true;//标记起点
dfs(0,0);
return 0;
}
【参考代码2】
#include <bits/stdc++.h>
using namespace std;
bool vis[10][10];
int a[200][2];
int d[4][2]={2,1,1,2,-1,2,-2,1}; //4个方向位移量
int sum;
void dfs(int x,int y,int n)
{
a[n][0]=x;//记录第n步到达的行数
a[n][1]=y;//记录第n步到达的列数
if(x==4 && y==8) //边界（到达终点）
{
sum++;//方案计数
cout<<sum<<":";//输出当前方案数
for(int i=1;i<=n;i++) //输出路径
{
if(i!=1) cout<<"->";
cout<<a[i][0]<<","<<a[i][1];
}
cout<<endl;
return ;
}
for(int i=0;i<4;i++)
{
int dx=x+d[i][0];//当前行
int dy=y+d[i][1];//当前列
if(dx>=0 && dx<=4 && dy>=0 && dy<=8 && !vis[dx][dy])//合法 没来过
{
vis[dx][dy]=true;//标记
dfs(dx,dy,n+1);//继续走
vis[dx][dy]=false;//回溯
}
}
}
int main() {
vis[0][0]=true;//标记起点
dfs(0,0,1);
return 0;
}
3、方格取数
4、特殊的质数肋骨
【题解】分离一个数的各个位，暴力枚举去掉最后一位后是否还是质数
【参考代码】
#include <bits/stdc++.h>
using namespace std;
int n;
bool is_prime(int x) //质数函数
{
if(x<=1) return false;
int a=sqrt(x);
for(int i=2;i<=a;i++)
{
if(x%i==0) return false;
}
return true;
}
void dfs(int x,int m)
{
if(m==n) //满足要求的位数就输出
{
cout<<x<<endl;
return ;
}
for(int i=1;i<=9;i++)
{
if(is_prime(x*10+i)) dfs(x*10+i,m+1); //生成的1位、2位、3位、4位数是质数，递归下去
}
}
int main() {
cin>>n;
dfs(0,0);//初始 位数
return 0;
}
【优化代码】
仔细观察，发现无论生成几位数，首位(一位数)必须为质数，一定是2，3，5，7之一，其他位数是1，3，7，9中的一个，因此复杂度可以大大的优化：
#include <bits/stdc++.h>
using namespace std;
int n;
int a[5]={2,3,5,7},b[5]={1,3,7,9};//首位 其他位
bool is_prime(int x) //质数函数
{
if(x<=1) return false;
int a=sqrt(x);
for(int i=2;i<=a;i++)
{
if(x%i==0) return false;
}
return true;
}
void dfs(int x,int m)
{
if(m==n) //满足要求的位数就输出
{
cout<<x<<endl;
return ;
}
for(int i=0;i<4;i++)
{
if(is_prime(x*10+b[i])) dfs(x*10+b[i],m+1); //生成的1位、2位、3位、4位数是质数，递归下去
}
}
int main() {
cin>>n;
for(int i=0;i<4;i++) //从首位开始递归下去
{
dfs(a[i],1);
}
return 0;
}
5、古希腊之争（二）
#include<iostream>
using namespace std;
char ch[25][25];
bool vis[25][25];
int d[4][2]={-1,0,0,1,1,0,0,-1};
int n,m,starx,stary,endx,endy,minn=0x3f;
void dfs(int x,int y,int t)
{
if(x==endx && y==endy) // 到达终点
{
minn=min(minn,t); //更新最短时间
return ;
}
for(int i=0;i<4;i++) // 4个方向
{
int dx=x+d[i][0];
int dy=y+d[i][1];
if(dx>=1 && dx<=n && dy>=1 && dy<=m && ch[dx][dy]!='K' && !vis[dx][dy]) //坐标合法，不是陷阱 没来过
{
vis[dx][dy]=true;//标记
if(ch[dx][dy]=='#') t++; //破墙壁 时间加1
dfs(dx,dy,t+1); //从当前为位置继续搜索
vis[dx][dy]=false; //回溯
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>ch[i][j];
if(ch[i][j]=='S') //记录起点位置
{
starx=i;
stary=j;
}
if(ch[i][j]=='T')//记录终点位置
{
endx=i;
endy=j;
}
}
}
vis[starx][stary]=true;//起点提前做好标记
dfs(starx,stary,0);//从起点开始搜索 当前时间0
if(minn!=0x3f) cout<<minn<<endl; // 输出
else cout<<"-1"<<endl; //无法到达
return 0;
}
6、素数环
#include <bits/stdc++.h>
using namespace std;
int a[15];
bool p[21],vis[15];
int n,cnt;
void print() //输出函数
{
cout<<++cnt<<":";
for(int i=1;i<=n;i++)
{
if(i!=1) cout<<" ";
cout<<a[i];
}
cout<<endl;
}
void check()//质数筛(质数标记为false)
{
p[1]=true;
for(int i=2;i<=20;i++)
{
for(int j=2;j<=20/i;j++)
{
p[i*j]=true;
}
}
}
void dfs(int m) //可爱的小搜搜
{
if(m==n+1) //边界：前n个数已确定
{
if(!p[a[m-1]+a[1]]) //最后一个数与第一个数之和为质数
{
print(); //哇！找到一个方案了啊，调用输出函数
}
return ;
}
for(int i=1;i<=n;i++) //遍历每一个数
{
if(!vis[i]) //你是i吗？你之前没被用过啊，先备用
{
if(m==1 || !p[i+a[m-1]]) //确定第一个数 无限制 或 i与前面相邻的数之和为素数
{
a[m]=i; // 恭喜你i，你被选中了，可以作为素数环的第m个数
vis[i]=true;//标记
dfs(m+1);//小搜搜，开始下一个吧！
vis[i]=false;//回溯
}
}
}
}
int main()
{
cin>>n;
if(n%2==1) //优化1：若n为奇数，不可能组成素数环
{
cout<<"total:"<<cnt<<endl;
return 0;
}
check();//优化2：先通过质数筛把质数保存下来
dfs(1); //从第一个数开始展开
cout<<"total:"<<cnt<<endl; //输出方案
return 0 ;
}
7、素数环2
#include <bits/stdc++.h>
using namespace std;
int a[22];
bool p[55],vis[22];
int n,cnt;
void print()
{
for(int i=1;i<=n;i++)
{
if(i!=1) cout<<" ";
cout<<a[i];
}
cout<<endl;
}
void check()
{
p[1]=true;
for(int i=2;i<=2*n;i++)
{
for(int j=2;j<=2*n/i;j++)
{
p[i*j]=true;
}
}
}
void dfs(int m)
{
if(m==n+1)
{
if(!p[a[m-1]+a[1]])
{
cnt++;
print();
if(cnt==10) exit(0);
}
return ;
}
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
if(!p[i+a[m-1]])
{
a[m]=i;
vis[i]=true;
dfs(m+1);
vis[i]=false;
}
}
}
}
int main()
{
cin>>n;
if(n%2==1) return 0;
check();
a[1]=1;
dfs(2);
return 0 ;
}
8、子集和求解
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> a,s;
bool vis[7010];
int n,k,cnt;
void dfs(int m,int ans)
{
if(m>=n || ans>k) return ; //边界
if(ans==k) //子集和等于k
{
cnt++; //方案数
for(int i=0;i<s.size();i++) //输出
{
cout<<s[i]<<" ";
}
cout<<endl;
if(cnt==1) exit(0); //输出第一种方案，直接结束程序
}
for(int i=m;i<a.size();i++) // 遍历每一个数
{
if(vis[i] || ans+a[i]>k) continue; //已用过 加上当前数已经大于k 直接结束当前循环
vis[i]=true;//标记
s.push_back(a[i]); //插入s数组
dfs(m+1,ans+a[i]);//搜索下一个
vis[i]=false;//回溯
s.pop_back();
}
}
int main()
{
cin>>n>>k;
int sum=0;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a.push_back(x);
sum+=x;
}
if(k>sum) //优化：总和比k还要小 无法实现
{
cout<<"No Solution!"<<endl;
return 0;
}
dfs(0,0);
cout<<"No Solution!"<<endl;
return 0;
}
9、单词接龙
10、湖计数
【题解】DFS判连通块问题，也可以用BFS来写
#include<iostream>
#include<cstdio>
using namespace std;
int fxx[9]={0,-1,-1,-1,0,0,1,1,1};//x方向
int fxy[9]={0,-1,0,1,-1,1,-1,0,1};//y方向
int n,m,ans;
char a[105][105];
void dfs(int x,int y)
{
int r,c;
a[x][y]='.';
for (int i=1;i<=8;i++)
{
r=x+fxx[i];
c=y+fxy[i];
if (r<1||r>n||c<1||c>m||a[r][c]=='.')//判断是否出界
continue;
a[r][c]='.';
dfs(r,c);
}
}
int main()
{
scanf("%d %d\n",&n,&m);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
cin>>a[i][j];
}
ans=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if (a[i][j]=='W')
{
ans++;
dfs(i,j);
}
}
}
printf("%d\n",ans);
return 0;
}
【后续提供视频讲解和标程】
前面课程连接
1、宽度优先搜索
2、深度优先搜索
3、回溯法-排列组合类
4、回溯法-切割问题与子集问题
5、回溯法-棋盘类问题
