1033-ambiguous dates.cpp

ZOJ 1033 Ambiguous Dates.主要运用年月日的表示和一点搜索技法.

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef struct _date{
	int year,month,day;
	bool operator ==(const _date &t) const
	{
		return year==t.year && month==t.month && day==t.day;
	}
}date;
//用来存放日期和到目的日期(2001-11-4)的差值
vector<date> d;
vector<int> v;
//用来存储输入,记录分割的字符串和日月年的字符串
char str[15],num[3][5],ymd[3][5];
//tl 日月年可能的数字的长度 , l 长度的具体情况
int TL[3]={2,2,3};
int L[3][3]={
	{1,2},
	{1,2},
	{1,2,4}
};
int cut[6][3]={
	{2,1,0},
	{2,0,1},
	{1,2,0},
	{1,0,2},
	{0,2,1},
	{0,1,2}
};
int m_d[12]={31,28,31,30,31,30,31,31,30,31,30,31};
//将字符串转化为数值
int Str2Int(char *s);
//判断是否是合法的日期
bool IsValid(date dd);
//判断是否包含分割符
bool IsDelimited(char *s);
//处理年月日的字符串
void Deal(char s[3][5]);
//计算到1700-1-1的天数差
int dif(date dd);
int main()
{
	int T;
	int cases=1,f,k,i,j,p,q,l0,l1,l2;
	char t[5];
	date end;
	freopen("1033.txt","r",stdin);
//	freopen("out.txt","w+",stdout);
	end.year=2001,end.month=11,end.day=4;
	scanf("%d",&T);
	while(T--)
	{
		d.clear();
		v.clear();
		scanf("%s",str);
		//如果包含分隔符
		if(IsDelimited(str))
		{
			//分割出字符串
			f=k=0;
			for(i=0;str[i]!='\0';i++)
			{
				if(str[i]>='0' && str[i]<='9')
					t[k++]=str[i];
				else
				{
					t[k]='\0';
					strcpy(num[f],t);
					k=0;
					f++;
				}
			}
			t[k]='\0';
			strcpy(num[f],t);
			//处理
			for(i=0;i<6;i++)
			{
				for(j=0;j<3;j++)
					strcpy(ymd[cut[i][j]],num[j]);
				Deal(ymd);
			}
		}
		//如果没有包含分隔符
		else
		{
			for(i=0;i<6;i++)
			{
				for(j=0;j<TL[cut[i][0]];j++)
					for(p=0;p<TL[cut[i][1]];p++)
						for(k=0;k<TL[cut[i][2]];k++)
						{
							l0=L[cut[i][0]][j];
							l1=L[cut[i][1]][p];
							l2=L[cut[i][2]][k];
							if(l0+l1+l2!=strlen(str))
								continue;
							//分割字符串
							f=0;
							for(q=0;q<l0;q++)
								num[0][q]=str[q];
							num[0][q]='\0';

							for(;q<l0+l1;q++)
								num[1][q-l0]=str[q];
							num[1][q-l0]='\0';

							for(;str[q]!='\0';q++)
								num[2][q-l0-l1]=str[q];
							num[2][q-l0-l1]='\0';
							for(q=0;q<3;q++)
								strcpy(ymd[cut[i][q]],num[q]);
							Deal(ymd);
						}
			}
		}
		printf("Scenario #%d:\n",cases++);
		//计算日期差
		k=dif(end);
		for(i=0;i<d.size();i++)
			v.push_back(dif(d[i])-k);
		sort(v.begin(),v.end());
		if(v.empty())
			printf("Illegal date\n");
		else
		{
			for(i=0;i<v.size();i++)
				printf("%d\n",v[i]);
		}
		printf("\n");
	}
	return 0;
}

bool IsDelimited(char *s)
{
	char ch;
	for(int i=0;*(s+i)!='\0';i++)
	{
		ch=*(s+i);
		if(ch=='/' || ch==92 || ch=='-' || ch==',' || ch=='.')
			return true;	
	}
	return false;
}

int Str2Int(char *s)
{
	int ret=0,i=0;
	while(*(s+i)!='\0')
	{
		ret=ret*10+*(s+i)-'0';
		i++;
	}
	return ret;
}

bool IsValid(date dd)
{
	if(dd.year<1700 || dd.year>2299)
		return false;
	if(dd.month>12 || dd.month<=0)
		return false;
	if(dd.month==2 && (dd.year%400==0 || (dd.year%100!=0 && dd.year%4==0)))
	{
		if(dd.day>29 || dd.day<=0)
			return false;
	}
	else
	{
		if(dd.day>m_d[dd.month-1] || dd.day<=0)
			return false;
	}
	return true;
}

void Deal(char s[3][5])
{
	date dd;
	int j,p,k;
	//年的长度为4
	if(strlen(s[2])==4)
	{
		dd.year=Str2Int(ymd[2]);
		dd.month=Str2Int(ymd[1]);
		dd.day=Str2Int(ymd[0]);
		if(!IsValid(dd))
			return;
		for(j=0;j<d.size();j++)
		{
			if(dd==d[j])
				break;
		}
		if(j==d.size())
			d.push_back(dd);
	}
	//年的长度为2或1
	else if(strlen(ymd[2])==2 || strlen(ymd[2])==1)
	{
		k=Str2Int(ymd[2]);
		dd.month=Str2Int(ymd[1]);
		dd.day=Str2Int(ymd[0]);
		for(j=17;j<=22;j++)
		{
			dd.year=100*j+k;
			if(!IsValid(dd))
				continue;
			for(p=0;p<d.size();p++)
			{
				if(dd==d[p])
					break;
			}
			if(p==d.size())
				d.push_back(dd);
		}
	}
}

int dif(date dd)
{
	int ret,i;
	//先求到 dd.year-1-1的天数差
	ret=(dd.year-1700)*365;
	if(2000<dd.year)
		ret++;
	//ret+=(dd.year/100-17)*24+dd.year%100/4;
	ret+=(dd.year/100-17)*24;
	if(dd.year%100!=0)
		ret+=(dd.year%100-1)/4;
	//再求到 dd.year-dd.month-1的天数差
	for(i=1;i<dd.month;i++)
		ret+=m_d[i-1];
	//再求到 dd.year-dd.month-dd.day
	ret+=dd.day-1;
	if(2<dd.month && (dd.year%400==0 || (dd.year%100!=0 && dd.year%4==0)))
		ret++;
	return ret;
}