Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 41 Solved: 19
[Submit][Status][Web
Board]
Description
Input
There will be at most 1000 test cases. Each case contains a command sequence with no more than 1000 characters.
Output
For each test case, print the case number, followed by minimal/maximal possible x (in this order), then the minimal/maximal possible y.
Sample Input
F?F
L??
LFFFRF
Sample Output
Case 1: 1 3 ⑴ 1
Case 2: ⑴ 1 0 2
Case 3: 1 1 3 3
HINT
Source
这个题嘛……那时候我还不会dp
大概是这样dp[pos][dir]:在pos这个位置，朝向dir时，最多能够给4个极限贡献多少
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
bool vis[int(1e4)+10][4];
struct node
{
int xmin,xmax,ymin,ymax;
}dp[int(1e4)+10][4];
int goal;
char s[int(1e4)+10];
node dfs(int pos,int dir)
{
if(vis[pos][dir])
return dp[pos][dir];
vis[pos][dir]=1;
dp[pos][dir].xmin=dp[pos][dir].xmax=dp[pos][dir].ymin=dp[pos][dir].ymax=0;
if(pos==goal)
{
if(s[pos]=='?')
{
if(dir==0)
dp[pos][dir].ymax=1;
else if(dir==1)
dp[pos][dir].ymin=⑴;
else if(dir==2)
dp[pos][dir].xmin=⑴;
else
dp[pos][dir].xmax=1;
}
else if(s[pos]=='F')
{
if(dir==0)
dp[pos][dir].ymin=dp[pos][dir].ymax=1;
else if(dir==1)
dp[pos][dir].ymin=dp[pos][dir].ymax=⑴;
else if(dir==2)
dp[pos][dir].xmin=dp[pos][dir].xmax=⑴;
else
dp[pos][dir].xmin=dp[pos][dir].xmax=1;
}
}
else
{
if(s[pos]=='L')
{
if(dir==0)
dp[pos][dir]=dfs(pos+1,2);
else if(dir==1)
dp[pos][dir]=dfs(pos+1,3);
else if(dir==2)
dp[pos][dir]=dfs(pos+1,1);
else
dp[pos][dir]=dfs(pos+1,0);
}
else if(s[pos]=='R')
{
if(dir==0)
dp[pos][dir]=dfs(pos+1,3);
else if(dir==1)
dp[pos][dir]=dfs(pos+1,2);
else if(dir==2)
dp[pos][dir]=dfs(pos+1,0);
else
dp[pos][dir]=dfs(pos+1,1);
}
else if(s[pos]=='F')
{
dp[pos][dir]=dfs(pos+1,dir);
if(dir==0)
{
dp[pos][dir].ymin++;
dp[pos][dir].ymax++;
}
else if(dir==1)
{
dp[pos][dir].ymin--;
dp[pos][dir].ymax--;
}
else if(dir==2)
{
dp[pos][dir].xmin--;
dp[pos][dir].xmax--;
}
else
{
dp[pos][dir].xmin++;
dp[pos][dir].xmax++;
}
}
else
{
node one,two,three;
three=dfs(pos+1,dir);
if(dir==0)
{
one=dfs(pos+1,2);
two=dfs(pos+1,3);
three.ymin++;
three.ymax++;
}
else if(dir==1)
{
one=dfs(pos+1,3);
two=dfs(pos+1,2);
three.ymin--;
three.ymax--;
}
else if(dir==2)
{
one=dfs(pos+1,1);
two=dfs(pos+1,0);
three.xmin--;
three.xmax--;
}
else
{
one=dfs(pos+1,0);
two=dfs(pos+1,1);
three.xmin++;
three.xmax++;
}
dp[pos][dir].xmin=min(min(one.xmin,two.xmin),three.xmin);
dp[pos][dir].xmax=max(max(one.xmax,two.xmax),three.xmax);
dp[pos][dir].ymin=min(min(one.ymin,two.ymin),three.ymin);
dp[pos][dir].ymax=max(max(one.ymax,two.ymax),three.ymax);
}
}
return dp[pos][dir];
}
int main()
{
int cs=0;
while(scanf("%s",s)!=EOF)
{
goal=strlen(s)⑴;
memset(vis,0,sizeof(vis));
node ans=dfs(0,3);
printf("Case %d: %d %d %d %d
",++cs,ans.xmin,ans.xmax,ans.ymin,ans.ymax);
}
}
