牛客网-乌龟跑步-（四维dfs）

时间：2021-03-11 15:37:35

链接：https://ac.nowcoder.com/acm/problem/15294
来源：牛客网

题目描述

有一只乌龟，初始在0的位置向右跑。
这只乌龟会依次接到一串指令，指令T表示向后转，指令F表示向前移动一个单位。乌龟不能忽视任何指令。
现在我们要修改其中正好n个指令（一个指令可以被改多次，一次修改定义为把某一个T变成F或把某一个F变成T）。
求这只乌龟在结束的时候离起点的最远距离。（假设乌龟最后的位置为x，我们想要abs(x)最大，输出最大的abs(x)）

输入描述:

第一行一个字符串c表示指令串。c只由F和T构成。
第二行一个整数n。
1 <= |c| <= 100, 1 <= n <= 50

输出描述:

一个数字表示答案。
示例1

输入

FT

1

输出

2
示例2

输入

FFFTFFF

2

输出

6
 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<math.h>

 #include<string>

 #define ll long long

 #define inf 0x3f3f3f3f

 using namespace std;

 string str;

 int n,ans,m,len;

 bool mp[][][][];///操作次数 剩余修改次数 位置 方向

 ///二维中0表示往回走，1表示往前走

 void dfs(int step,int s,int x,int d)///操作到哪个指令 剩余修改指令次数 当前位置 方向

 {

     if(s<) return ;///dfs递归进来后，修改次数不够

     int flag;

     if(d==-)

         flag=;///往回走

     else

         flag=;///往前走

     if( mp[step][s][x+][flag] )  return;///如果这套状态之前的dfs中走出现过，直接返回，因为以前已经往不同情况dfs过了

     mp[step][s][x + ][flag] = true;///标记出现过的情况

     if(step==len)///指令已经操作完了，可以结束了

     {

         if(s%==) ///如果修改指令的次数还剩偶数次，这个答案是可行的，否则不行

             ans=max(ans,abs(x));

         return;

     }

     if( str[step]=='T' )///常规操作是转身

     {

         dfs(step+,s-,x+d,d);///执行操作指令step+1，修改指令后s-1，改成F会走动，方向不变

         dfs(step+,s,x,-d);///执行操作指令step+1， 不修改指令，

     }

     else

     {

         dfs(step+,s,x+d,d);

         dfs(step+,s-,x,-d);

     }

 }

 int main()

 {

     while(cin>>str>>n)/// TF串，F表示前进一格，   T表示转身，但是不走动

     {

         ///n表示可以修改指令的次数,一定要修改

         len=str.size();

         memset(mp,false,sizeof(mp));

         ans=-;

         dfs(,n,,);///起始方向为正

         printf("%d\n",ans);

     }

     return ;

 }

相关文章