记录编号	47204	评测结果	AAAAAAAAAA
题目名称	[Poetize 9] 升降梯上	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.398 s
提交时间	2012-10-31 10:44:11	内存使用	3.42 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int MAXNUM=1000000000;

int zero,change[22],tim[1010][22],rec[20010][2];
bool used[20010][2];

int absint(int num)
{
	if (num<0)
		return(-num);
	return(num);
}

int main(void)
{
	freopen("updown.in","r",stdin);
	freopen("updown.out","w",stdout);
	int i,j,n,m,top=0,topt,timnow=0,timmax=0;
	cin>>n>>m;
	for (i=1;i<=m;i++)
	{
		cin>>change[i];
		if (change[i]==0)
			zero=i;
	}
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			tim[i][j]=MAXNUM;
	tim[1][zero]=0;
	rec[0][0]=1;
	rec[0][1]=zero;
	while (1==1)
	{
		for (i=1;i<=m;i++)
			if (tim[n][i]==timnow)
			{
				cout<<timnow<<endl;
				return(0);
			}
		if (timnow>timmax)
		{
			cout<<"-1\n";
			return(0);
		}
		topt=top;
		for (i=0;i<=topt;i++)
		{
			if (tim[rec[i][0]][rec[i][1]]==timnow)
			{
				if (rec[i][1]-1>=1)
					if (tim[rec[i][0]][rec[i][1]-1]>timnow+1)
					{
						tim[rec[i][0]][rec[i][1]-1]=timnow+1;
						rec[++top][0]=rec[i][0];
						rec[top][1]=rec[i][1]-1;
						if (timmax<timnow+1)
							timmax=timnow+1;
					}
				if (rec[i][1]+1<=m)
					if (tim[rec[i][0]][rec[i][1]+1]>timnow+1)
					{
						tim[rec[i][0]][rec[i][1]+1]=timnow+1;
						rec[++top][0]=rec[i][0];
						rec[top][1]=rec[i][1]+1;
						if (timmax<timnow+1)
							timmax=timnow+1;
					}
				if (change[rec[i][1]])
				{
					if (rec[i][0]+change[rec[i][1]]>=1&&rec[i][0]+change[rec[i][1]]<=n)
					{
						if (tim[rec[i][0]+change[rec[i][1]]][rec[i][1]]>timnow+2*absint(change[rec[i][1]]))
						{
							tim[rec[i][0]+change[rec[i][1]]][rec[i][1]]=timnow+2*absint(change[rec[i][1]]);
							rec[++top][0]=rec[i][0]+change[rec[i][1]];
							rec[top][1]=rec[i][1];
							if (timmax<timnow+2*absint(change[rec[i][1]]))
								timmax=timnow+2*absint(change[rec[i][1]]);
						}
					}
				}
			}
		}
		timnow++;
	}
	return(0);
}