四维dfs

• 从题目中我们可以知道有四个变量得考虑——目前所在字符串中的位置，剩余的操作步数，目前乌龟所在位置及乌龟行进方向，故我们可以想到（看大佬的）开个四维数组进行dfs遍历所有情况。下面我们来看代码

  #include<bits/stdc++.h>
  using namespace std;
  string h;
  int n;
  int length;
  bool dp[105][55][205][2];
  int ans=0;
  void dfs(int def,int n,int pos,int way)
  {
    if(def==length)//当走到字符串最末尾的时候
    {
        if((n%2)==0) ans=max(ans,abs(pos));
  //判断是否升沿步骤数是2的倍数，因为只要是2的倍数，随便选取一个，
  //比如F,先改为T，再改为F，每改两次便会回到原来的，
  //故只要是2的倍数就能保证和剩余0操作步骤是一样的。
        return;
    }
    if(n<0||dp[def][n][pos+105][way]) return;//如果操作步数小于0说明到头了，注意这里不能写
  //n<=0，因为存在着这样一种情况，当操作步数为0时候，字符串还没有走完，故不能停止。
    dp[def][n][pos+105][way]=1;//标记目前的状态，下次再到该状态的时候便停止
    if(h[def]=='F')
    {
        if(way==0)
        {
            dfs(def+1,n-1,pos,1);
                      //改变：字符串向前，操作数-1，位置不便（由前进变为改方向），方向变为正向1
            dfs(def+1,n,pos-1,0);
                     //不改变：字符串向前，操作数不变，位置向后退，方向不变保持负方向
        }
        else
        {
            dfs(def+1,n-1,pos,0);
                     //改变：字符串向前，操作数-1，位置不便（由前进变为改方向），方向变为负向0
            dfs(def+1,n,pos+1,1);
                     //不改变：字符串向前，操作数不变，位置向前进，方向不变保持正方向
        }
    }
    else
    {
        if(way==0)
        {
            dfs(def+1,n-1,pos-1,0);
            dfs(def+1,n,pos,1);
        }
        else
        {
            dfs(def+1,n-1,pos+1,1);
            dfs(def+1,n,pos,0);
        }
    }
  

}
int main()
{
cin>>h>>n;
length=h.size();
memset(dp,0,sizeof(dp));//先初始化为0
dfs(0,n,0,1);//开始字符串位置在0，有n个操作次数，乌龟位置为0，方向为正方向1
cout<<ans<<endl;
}
```