csu1510: Happy Robot

浏览数：23 / 时间：2015年06月11日

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 1
Case 2: -1 1 0 2
Case 3: 1 1 3 3

HINT

Source

湖南省第十届大学生计算机程序设计竞赛

这个题嘛……那时候我还不会dp

大概是这样dp[pos][dir]:在pos这个位置，朝向dir时，最多能够给四个极限贡献多少

#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=-1;
			else if(dir==2)
				dp[pos][dir].xmin=-1;
			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=-1;
			else if(dir==2)
				dp[pos][dir].xmin=dp[pos][dir].xmax=-1;
			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)-1;
		memset(vis,0,sizeof(vis));
		node ans=dfs(0,3);
		printf("Case %d: %d %d %d %d\n",++cs,ans.xmin,ans.xmax,ans.ymin,ans.ymax);
	}
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

csu1510: Happy Robot