DFS
一般搜索算法的流程框架
1.定义点集X为已经处理的点，点集F为已发现但尚未处理的点
2.初始化点击X为空，点集只包含搜索的起点
3.只要点集F不为空，循环4~6
4.从点集F中取出一个点v
5.处理点v，把点v加入点击X
6，遍历v的出边，对于每个v的邻居，若既不在点集X中也不再点集F中，则加入点集F
7.搜索结束，带点集X里的点是搜索过的点
先进后出:栈处理
简单解读: 每一个点位，找到附近的邻接点，表示发现但未处理的,将其放入栈中，由于栈是先进后出，
拿第一个栈元素作为搜索点，若是该点的临界点中已经有加入栈的元素，则这个临界点不能再放入栈，
也就是不能从该点访问这个邻接点，依此类推，直到所有点都被访问过，或是找到答案退出。
递归处理
简单解读:F为当前点的邻接点并且还没有搜过，X表示已经搜过并且标记过的点
每到达一个点，搜索它的临界点的其中一个，走完之后标记这个点表示已经走过
，若是这条路不同走不了了，点位就回溯，回到之前的点，继续找没走过的点
（即没有标记过的点），直到回到起点，再找除了这个点以外的其他没走过的支路，
按照之前的走法直到全部走完，或是找到答案后退出
递归DFS的流程框架
1.定义点集X为已经处理的点，
2.初始化点集为空
3.递归搜索点v(开始时搜索起点)
5.处理点v，把点v加入点集X
6.循环v的出边，对于每个v的邻居，则递归处理那个点
7.搜索结束，点集X里的点是搜索过的点
1-2-4
|
3
栈处理:处理顺序不可能1 2 3 4
递归处理:处理顺序有可能1 2 3 4
*/
/*
DFS迷宫可达问题
有一个大小为n*m的二维迷宫，其中#用来表示墙壁，
*用来表示有路可走，每一次可向上走左右的任一方向走一步，
问从左上角出发可否走到右下角。**####
#**###
##**##
###**#
####**该题目的数据范围较小，顾客考虑暴力搜索，每一次从一个没有
走过的点出发尝试向四周走，若可以走就一直走下去
我们每次都是选择一个没有被到达过的点开始，进行下一步的尝试，这个尝试是不是很像for循环?但是怎么确定这个点有没有被到达过呢，我们需要一个二维标记数组，来表示，初始化为0，若该店已被到达过，则置为1
进行一次常识的话只需要一个for循环即可，但是我们需要进行的可是若干次尝试，是不是很像递归函数我们用函数bool dfs(int x,iny y)来表示从点（x,y）出发是否可以到达终点，可行则返回1，否则返回0
*/#include<bit/stdc++.h>
using namespace std;const int maxn=505;//存图数组最大长度
int dx[4]={0,0,-1,1};//四个方向
int dy[4]={1,-1,0,0};
int mapp[maxn][maxn];//存图
int flag[maxn][maxn];//是否走过
bool check(int x,int y){//检查该点是否合法
if(x>0&&y>0&&x<n&&y<n&&mapp[x][y]=='*'&&flag[x][y]==0){
return true;
return false;
}
}int edx,edy; //终点的坐标
bool dfs(int x,int y){
if(!check(x,y)){//不合法，返回false
return false;
}
if(x==edx&&y==edy)//合法且等于终点，返回true
return true;
flag[x][y]=1;//合法但不是终点，标记该点
for(int i=1;i<4;i++){//上下左右四个方向各自遍历
if(dfs(x+dx[i],y+dy[i]))
return true; //若是找到终点，返回true，如此便一直到返回到dfs结束
}
return false;
}
int main(){
int x,y;
scanf("%d%d%d%d",&x,&y,&edx,&edy);
if(dfs(x,y))
scanf("true");
else{
scanf("false");
}
}
连通块问题
多加四个方向，从上下左右四个方向加上左上，左下，右上，右下四个方向
不需要flag数组标记，走过就消除该点
找有多少个联通区域
#include<bit/stdc++.h>
using namespace std;const int maxn=505;//存图数组最大长度
int dx[4]={0,0,-1,1,1,1,-1,-1};//四个方向
int dy[4]={1,-1,0,0-1,1,1,-1};
char mapp[maxn][maxn];//存图
bool check(int x,int y){//检查该点是否为联通区域
if(x>0&&y>0&&x<n&&y<n&&mapp[x][y]=='@'){
return true;
return false;
}
}bool dfs(int x,int y){
if(!check(x,y)){//不是就停止往下走
return;
}
mapp[x][y]='*';//走过就消除
for(int i=0;i<8;i++){//八个方向各自遍历
dfs(x+dx[i],y+dy[i]);
}}
int main(){
int count=0;
string c;
for(int i=0;i<n;i++){
cin>>c;
mapp[i]=c;
}//输入图
for(int x=0;x<n;x++)
{
for(int y=0;y<n;y++){
if(mapp[x][y]=="@"){
count++;//记录连通区域的数量
dfs(x,y);//消除这一块儿联通区域
}
}
}
}
BFS
//广度(宽度)优先搜索 （BFS）
广度优先，层次遍历，一层一层扩展
BFS的实现方法
通常采用STL容器中的队列queue实现
当向队列中压入一个元素时，就像排队一样，新来的要排在末尾，
当队列中取出一个元素时，取出的是队列中最早压入的那个，
就像排队，先来的先走，所以队列的性质可以用四个字概括，先进先出
起点先入队，再出队，将起点临阶的点入队，
再出队一个元素，再将这个元素邻接的还没入队的元素入队
/*
#include<queue>
queue<int>q;
q.push(3);
*/
/*
给出一个大小为n*n的01方阵，如果两点间为0表示这是一条路，1表示一面墙壁，
现在要求你从方针左上角走到右下角，输出最短的经过的路径，保证答案唯一比如这就是一个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 0 [0]
显然最短路径就是[]包围起来的那么为了解决这道题我们首先应该解决最短路径，然后再这过程中记录路径即可
这道题有一个性质，那就是相邻点的转移只花费1的代价，而bfs便可以在这种条件下解决最短性质问题
我们先抛开记录路径这一说，只考虑如何使路径最短
按照层序遍历的思想，是不是如果有一个状态，先前出现过了，之后再出现的话，花费的代价一定比之前的大，
因为先前的状态在搜索树中的层更偏上一点
所以我们开一个bool vis[][]来记录这个状态有没有出现过，减少搜索规模也同时保证答案的正确性
一个（x,y）的点可以向上下左右个扩展一次，花费代价均为1，所以我们对于每个点都要尝试进行四个方向的扩展，
最终就一定嫩遍历到终点
而且根据答案最优性，一个状态最优是不是保证被较前的一个状态扩展到便可行
所以当一个（x2,y2）被（x1,y1）扩展到的时候，我们记录他的步数等于step[x2][y2]=step[x][y]+1
一个点只被有效入队一次,有效出队一次，有n*n个点，复杂度便是O（n*n）*/
//由于BFS是一层层的遍历，因此不会出现一条路走到终点，但不是最短路径的情况。
#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int mapp[maxn][maxn];//存图
int step[maxn][maxn];//层数，到起点的最短举例
int vis[maxn][maxn];//是否走过
int n,m;
bool check(int x,int y){//是否可走，且没被标记过
if(x>0&&x<=n&&y>0&&y<=m&&mappp[x][y]==0&&vis[0][0]==0){
return true;
}
return false;
}
int dx[4]={0,0,1,-1};//四个方向
int dy[4]={1,-1,0,0};
typedef pair<int,int>PII;//重命名PII记录坐标x，y
queue<PII>qq;//关于x，y的队列
PII st,ed;//起点，终点
int bfs(int x,int y){
//如果有多个BFS，记得清空队列，避免下一次BFS延续上一次的点
while(!qq.empty()){
qq.pop();
}
qq.push(st);//起点入队
vis[st.first][st.second]=1;//标记起点
step[st.first][st.second]=0;//起点步数为0
while(!qq.empty()){//入队，出队如此循环，便可遍历完整个图
PII t=qq.front();//从起点开始，出队
qq.pop();
if(t.first==ed.first&&t.second==ed.second){//每一个出队的元素都检查一遍是否到达终点
return step[t.first][t.second];//若是到达返回步数
}
for(int i=0;i<4;i++){//四个方向走
int xx=t.first+dx[i];
int yy=t.second+dy[i];
if(check(xx,yy))
{
qq.push(make_pair(xx,yy));//将xx,yy变成pair入队，用make_pair(int,int);
vis[xx][yy]=1;//标记
step[xx][yy]=step[st.first][st.second]+1;//步数+1
}
}
}
return -1;
}
int main(){
int T;
rteurn 0;
}
//如果要记录路径怎么办？
刚才我们有提到，一个状态只会被有效扩展一次，那么我们只要记录这个点被谁扩展到即可，
我们只需要从终点开始不断访问他的前驱节点即可，当然由于是反正推到终点的，
所以我们应该将这些点放到栈中再弹出即可
开一个pair<int,mint>fre来记录即可
最终只需要从终点反推去起点即可
while(en.first!=0||en.second!=0){//将前一个点位入栈，到起点为止
s.push(en);
en=fre[en.first][en.second];//更新前一个扩展的点位
}
s.push(make_pair(0,0));//最后再将起点入栈
while(!s.empty()){
cout<<s.top().first+1<<" "<<s.top().second+1;//输出
s.pop();//出栈
}
/*
题目大意:
有一个三维迷宫，求起点'S'到'E'的最少需要走几步，如果起点和终点不
连通免责输出"Trapped！"解题策略:
可以利用BFS按层搜索的性质，从起点'S'出发开始搜索，
记录每个节点所在的层数，若终点'E'在第k层，则起点'S'到终点'E'的距离是k
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=505;int maxp[maxn][maxn][maxn];//存三维迷宫
int step[maxn][maxn][maxn];//步数
int vis[maxn][maxn][maxn];//记录
int n,m;
bool check(int x,int y,int z){//判断
if(x>0&&x<=n&&y>0&&y<=n&&z>0&&z<=n&&mapp[x][y][z]==0&&vis[x][y][z]==0)
return true;
return false;
}int dx[6]={0,0,1,-1,0,0};//方向
int dy[6]={1,-1,0,0,0,0};
int dz[6]={0,0,0,0,1,-1};
typedef pair(int,int)PII;
struct Node{//结构体，存坐标
int x,y,z;
Node(int a,int b,int c){//初始化结构体
x=a;
y=b;
z=c;
}
};queue<Node> qq;
Node st;
int bfs(int x,int y){
qq.push(st);
while(!qq.empty()){
Node t=qq.front();
qq.pop();
if(t.x==edx&&t.y==edy&&t.z==edz){//判断出队的是不是终点
return step[t.x][t.y][t.z];
}
for(int i=0;i<6;i++){
int xx=t.x+dx[i];
int yy=t.y+dy[i];
int zz=t.z+dz[i];
if(check(xx,yy,zz)){
qq.push(Node(xx,yy,zz));
vis[xx][yy][zz]=1;
step[xx][yy][zz]=stap[t.x][t.y][t.z]+1;//步数加1
}
}
}
return -1;
}
问题:
N个城市,编号1到N，城市间有R条单项道路，每条道路连接两个城市，有长度和过路费两个属性，Bob只有k块钱，他想从城市1走到城市N，问最短共需要走多长的路，如果到不了N，输出-1
思路:从城市1开始深度优先遍历整个图，找到所有能过到达N的走法，选一个最优的
如何剪枝:
1.最优化剪枝:如果当前已经找到的最优路径长度为L，那么在继续搜索的过程中，总长度已经大于等于L的走法，就可以直接放弃了，不用走到底了
2.可行性剪枝:如果当前到达城市的路费已大于k,或者等于k且没有到达终点，就可以直接放弃了
