搜索

很多题目正解都很难想到，所以可以用一种万能的方法：搜索

搜索分为两种，一种是广度优先搜索（bfs),深度优先搜索（dfs）

广搜：

假设你要寻找的答案存在于第3层中的第4个，只有一个答案

那么我们可以首先寻找第一层，发现只有一个点，那么判断是不是答案，很明显不是

那么再寻找第二层，有两个点，遍历这两个点，判断是否有答案，在这个图中间，这两个点中间没有答案

然后寻找第三层，共有四个点，遍历这四个点，发现答案存在于第四个点，找到答案之后，第四层就不用寻找了

大致思路如上，那到底该如何用代码实现呢？

用一个数组存每次遍历的数字和位置，这里用q[i][0]表示第i个点的数值，q[i][1]表示第i个点的位置

用两个指针，head（头指针）和tail（尾指针），head表示遍历的这个点的上一次遍历的点

res[i]作为标记数组，为了防止死循环

模板如下：

/*
ans表示寻找的答案，num[i]表示每一个数的数值 ,res[i]作为标记数组 
*/
head=0;tail=1;q[1][0]=num[1];q[1][1]=1;res[1]=1;
while(head^tail){
    head++;
    for(int i=1;i<=number;i++){
        if(mapp[q[head][1]][i]&&!res[i]){
            res[i]=1;tail++;q[tail][0]=num[i];q[tail][1]=i;
            if(num[i]==ans){
                printf("答案存在于第%d个点",i);
            }
        }
    }
}

时间复杂度为O（n^2）;（此题较为特殊，因为每一次还要寻找与之相邻的点，寻常复杂度为O（n））

深搜：

还是那张图，同样的题目

之前的广度优先搜索是没每层每层寻找的，而这个是每个每个寻找的

还是从第一个开始寻找，发现不是答案

那么寻找它的子节点（从左至右，从右到左也可以），先寻找第二层第一个节点

发现依然不是答案，再寻找这个点的最左边的节点，即第三层第一个点

以此类推，找到了第四行第一个点，但此时还不是答案

这是涉及到一个重要的操作：回溯

从当前节点返回到它的父节点，第三层第一个点

回溯之后，判断当前的点有没有其他的子节点，如果有则遍历的这个子节点

否则就继续回溯，如图，如果要遍历所有的点，路径如下（图画的有点丑）：

路径左边的箭头表示寻找的顺序，右边的表示回溯

可以看出，时间复杂度为O（n^2)（但这道题为n^3，还是因为每次需要寻找与之相邻的点）

代码如下：

void dfs(int x){
    res[x]=1;//标记
    if(num[x]==ans){
        printf("答案存在于第%d个点",i);return;
    } 
    for(int i=1;i<=number;i++)
       if(mapp[x][i]&&!res[x]){
           dfs(i);//往下搜素 
        res[i]=0;//回溯 
       }
}

总结：

广度优先搜索优点是耗时小，但耗空间

深度优先搜索优点是省空间，代码短，但耗时间

例题：

题目描述

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $\le i \le N)(1≤i≤N)上有一个数字K_i(0 \le K_i \le N)Ki(0≤Ki≤N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3, 3 ,1 ,2 ,53,3,1,2,5代表了K_i(K_1=3,K_2=3,…)Ki(K1=3,K2=3,…)，从11楼开始。在11楼，按“上”可以到44楼，按“下”是不起作用的，因为没有-2−2楼。那么，从AA楼到BB楼至少要按几次按钮呢？$

输入格式

共二行。

第一行为

第二行为 $N个用空格隔开的非负整数，表示K_iKi。$

输出格式

一行，即最少按键次数,若无法到达，则输出

输入输出样例

输入 #1

5 1 5
3 3 1 2 5

输出 #1

3

AC代码：
广搜：

#include<bits/stdc++.h>
using namespace std;

int start,number,need,num[302],res[3002];
int dx[3]={-1,1},hd,tl,q[300002][3],fh=0;

void bfs(int now){
    res[now]=1;hd=0;tl=1;q[tl][1]=now;q[tl][2]=0;
    while(hd^tl){
        hd++;
        for(int i=0;i<2;i++){
            int nx=q[hd][1]+dx[i]*num[q[hd][1]];
            if(nx>=1&&nx<=number&&!res[nx]){
                tl++;q[tl][1]=nx;q[tl][2]=q[hd][2]+1;res[nx]=1;
            }
            if(nx==need){
                fh=1;return;
            }
        }
    }
}

int main(){
    cin>>number>>start>>need;
    for(int i=1;i<=number;i++)cin>>num[i];
    bfs(start);
    if(start==need)cout<<0;
    else{
    if(fh)cout<<q[tl][2];
    else cout<<-1;
    }
    return 0;
}

深搜：

#include<bits/stdc++.h>
using namespace std;

int start,number,num[3002],last,res[3002],flag=0,ans=1e9;

int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

void dfs(int x,int sum){
    if(x==last)ans=min(ans,sum);
    else if(sum<=ans){
      res[x]=1;
      if(x+num[x]<=number&&!res[x+num[x]])dfs(x+num[x],sum+1);
      if(x-num[x]>=1&&!res[x-num[x]])dfs(x-num[x],sum+1);
      res[x]=0;
    }
} 

int main(){
    number=read();start=read();last=read();
    for(int i=1;i<=number;i++)num[i]=read();
    if(start==last){
        printf("0");return 0;
    }
    dfs(start,0);
    if(ans!=1e9)printf("%d",ans);
    else printf("-1");
    return 0;
}