一、深度优先搜索
定义
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。
解决题形
1.迷宫类深搜
C o d e Code Code
#include<bits/stdc++.h>
using namespace std;
char a[110][110];
int n,m;
//设置两个数组，表示x和y下标值的变化
int fx[5] = {0,0,1,0,-1};
int fy[5] = {0,1,0,-1,0};
//将下标为xy的水塘W，改成草地.
void dfs(int x,int y){
a[x][y] = '.';
int tx,ty;
//循环递归四个方向
for(int i = 1;i <= 4;i++){
tx = x + fx[i];
ty = y + fy[i];
//如果要去的点是水塘W，且没出边界
if(a[tx][ty]=='W') dfs(tx,ty);
}
}
int main() {
cin>>n>>m;
int i,j,c = 0;
for(i = 1;i <= n;i++){
for(j = 1;j <= m;j++){
cin>>a[i][j];
}
}
//遍历每个点，如果是W计数器+1，且将整片相邻池塘改成草地
for(i = 1;i <= n;i++){
for(j = 1;j <= m;j++){
if(a[i][j] == 'W'){
c++;
dfs(i,j);
}
}
}
cout<<c;
return 0;
}
2.数值类深搜
C o d e Code Code
#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int a[110];
string t="+-*";
bool f=false;
void fun(string s){
string r=s;
int b[110]={0};
for(int i=0;i<4;i++){
b[i]=a[i];
}
for(int i=0;i<s.size();i++){
if(s[i]=='*'){
b[i+1]*=b[i];
b[i]=0;
if(i==0)s[i]='+';
else s[i]=s[i-1];
}
}
// for(int i=0;i<4;i++){
// cout<<b[i]<<" ";
// }
// cout<<endl;
// cout<<s<<endl;
for(int i=0;i<s.size();i++){
if(s[i]=='+'){
b[i+1]+=b[i];
}else{
b[i+1]=b[i]-b[i+1];
}
}
if(b[3]==24)f=true;
// cout<<a[0]<<r[0]<<a[1]<<r[1]<<a[2]<<r[2]<<a[3]<<"="<<b[3]<<endl;
}
void dfs(string s){
if(s.size()==3){
// cout<<s<<endl;
fun(s);
return;
}
for(int i=1;i<=3;i++){
dfs(s+t[i-1]);
}
}
int main(){
// dfs("");
// return 0;
// a[0]=1;a[1]=2;a[2]=3;a[3]=4;
// fun("--+");
// return 0;
cin>>n;
while(n--){
for(int i=0;i<4;i++){
cin>>a[i];
}
f=false;
dfs("");
if(f)cnt++;
}
cout<<cnt;
return 0;
}
例题
1431: 【基础】迷宫的第一条出路
C o d e Code Code
#include<bits/stdc++.h>
using namespace std;
int n;
char a[30][30];
int r[400][3];
int fx[5]={0,0,-1,0,1};
int fy[5]={0,-1,0,1,0};
void print(int k){
for(int i=1;i<=k;i++){
printf("(%d,%d)",r[i][1],r[i][2]);
if(i!=k){
cout<<"->";
}
}
exit(0);
}
void dfs(int x,int y,int k){
r[k][1]=x;
r[k][2]=y;
a[x][y]='1';
if(x==n&&y==n){
print(k);
}
int tx,ty;
for(int i=1;i<=4;i++){
tx=x+fx[i];
ty=y+fy[i];
if(a[tx][ty]=='0'){
dfs(tx,ty,k+1);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
dfs(1,1,1);
return 0;
}
1430: 【基础】迷宫出口
C o d e Code Code
#include<bits/stdc++.h>
using namespace std;
int n,a[110][110],s1,s2,e1,e2;
int fx[5]={0,0,1,0,-1};
int fy[5]={0,1,0,-1,0};
bool f;
void dfs(int x,int y){
a[x][y]=1;
int tx,ty;
for(int i=1;i<=4;i++){
tx=x+fx[i];
ty=y+fy[i];
if(tx==e1&&ty==e2){
f=true;
}else if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]==0){
dfs(tx,ty);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
cin>>s1>>s2>>e1>>e2;
if(a[s1][s2]==1||a[e1][e2]==1){
cout<<"NO";
return 0;
}
dfs(s1,s2);
if(f){
cout<<"YES";
}else{
cout<<"NO";
}
return 0;
}
1850: 【提高】和为T
C o d e Code Code
#include<bits/stdc++.h>
#define R register
using namespace std;
int n,a[40],t,c,f[40];
void dfs(int k){
int sum=0;
bool flag=false;
if(k==0){
for(R int i=1;i<=n;i++){
if(f[i]==1){
flag=true;
sum+=a[i];
}
}
if(sum==t&&flag){
c++;
for(R int i=1;i<=n;i++){
if(f[i]==1){
cout<<a[i]<<" ";
}
}
cout<<endl;
// cout<<sum<<endl;
}
return;
}
f[k]=0;
dfs(k-1);
f[k]=1;
dfs(k-1);
}
template <typename T> void read(T &t){
t=0;
char ch=getchar();
int f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
do{
(t*=10)+=ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
t*=f;
}
int main(){
read(n);
for(R int i=1;i<=n;i++){
read(a[i]);
}
read(t);
dfs(n);
cout<<c;
return 0;
}
二、广度优先搜索
定义
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
解决题形
1.迷宫类广搜
C o d e Code Code
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[50][50];
int q[2500][4];
int head=1,tail=1;
int tx,ty;
int fx[]={0,0,1,0,-1};
int fy[]={0,1,0,-1,0};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
q[1][1]=1;
q[1][2]=1;
q[1][3]=1;
while(head<=tail){
for(int i=1;i<=4;i++){
tx=q[head][1]+fx[i];
ty=q[head][2]+fy[i];
if(a[tx][ty]=='.'){
q[++tail][1]=tx;
q[tail][2]=ty;
q[tail][3]=q[head][3]+1;
if(tx==n&&ty==m){
cout<<q[tail][3];
return 0;
}
a[tx][ty]='#';
}
}
head++;
}
return 0;
}
例题
1443: 【提高】泉水
C o d e Code Code
#include<bits/stdc++.h>
using namespace std;
int n,m,p1,p2;
int a[1010][1010];
int q[1000100][3];
bool f[1010][1010];
int fx[]={0,0,1,0,-1};
int fy[]={0,1,0,-1,0};
int head=1,tail=1;
int main(){
cin>>n>>m>>p1>>p2;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
q[1][1]=p1;
q[1][2]=p2;
f[p1][p2]=true;
while(head<=tail){
for(int i=1;i<=4;i++){
int tx=q[head][1]+fx[i];
int ty=q[head][2]+fy[i];
if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!f[tx][ty]&&a[tx][ty]<=a[p1][p2]){
tail++;
q[tail][1]=tx;
q[tail][2]=ty;
f[tx][ty]=true;
}
}
head++;
}
// for(int i=1;i<=tail;i++){
// cout<<q[i][1]<<" "<<q[i][2]<<endl;
// }
cout<<tail;
return 0;
}