青蛙

这道题其实是我练习dp的时候看到的，这道题应该归在dp里吗？？（可能是我太菜了dp不会做吧。。。）我直接用dfs做了，还是比较容易的一道dfs题目。
思路：dfs每一步的坐标，三种情况 ：1.向前一步 2.向后一步 3.如果有隧道，进入隧道。附上代码应该还是很好懂的。

#include<bits/stdc++.h>
using namespace std;
int mp[300];
int n,m;
int ans=INT_MAX;
bool vst[300];
void dfs(int x,int p)
{
   if(x==m)
    {
        ans=min(ans,p);
        return;
    }
    if(p>ans||x<0)   return;
    if(vst[x+1])
    {
        vst[x+1]=false;
        dfs(x+1,p+1);
        vst[x+1]=true;
    }
    if(x-1>=0&&vst[x-1])
    {
        vst[x-1]=false;
        dfs(x-1,p+1);
        vst[x-1]=true;
    }

    if(mp[x]!=-1&&vst[mp[x]])
    {

        vst[mp[x]]=false;
        dfs(mp[x],p+1);
        vst[mp[x]]=true;
    }

}
int main()
{
    cin>>m>>n;
    memset(mp,-1,sizeof(mp));
    memset(vst,true,sizeof(vst));
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        mp[x]=y;
    }
    vst[0]=false;
    dfs(0,0);
    cout<<ans;
    return 0;
}