k.cpp

ACM World Final 2008题目程序代码

#include <cstdio>
#include <cstring>
using namespace std;

const int ed[4][3]={{0,0,0},{-1,0,0},{0,0,1},{0,-1,1}};
const int vd[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int mr,mc,sr,sc,tr,tc,e[110][110][2];
int dis[110][110][4][2];

const int M=131072;
struct qnode
{
	int r,c,d,f;
	qnode& operator()(int r_,int c_,int d_,int f_)
	{
		return r=r_,c=c_,d=d_,f=f_,*this;
	}
	void dealnode();
} q[M];
int qs,qt;
bool inq[110][110][4][2];

void addnode(int r,int c,int d,int f,int dis_)		
{
	dis[r][c][d][f]=dis_;
	if(bool &inqn=inq[r][c][d][f])return;
	else inqn=true;
	int dis_s=dis[q[qs].r][q[qs].c][q[qs].d][q[qs].f];
	if(dis_>dis_s)q[qt](r,c,d,f),qt=qt+1&M-1;
	else q[qs=qs-1&M-1](r,c,d,f);
}

void qnode::dealnode()
{
	int disn=dis[r][c][d][f];
	int rb=r-vd[d][0]+ed[d][0],cb=c-vd[d][1]+ed[d][1];
	int eb=e[rb][cb][ed[d][2]];
	for(int i=0;i<4;++i)
		if(e[r+ed[i][0]][c+ed[i][1]][ed[i][2]])
		{
			bool f1=d!=i;
			int dis1=disn+(eb<<(f|f1)),r1=r+vd[i][0],c1=c+vd[i][1];
			if(dis1<dis[r1][c1][i][f1])addnode(r1,c1,i,f1,dis1);
		}
	inq[r][c][d][f]=false;
}

int main()
{
	for(int te=1;scanf("%d %d",&mr,&mc),mr;++te)
	{
		scanf("%d %d %d %d",&sr,&sc,&tr,&tc);
		memset(e,0,sizeof(e));
		for(int i=1;;++i)
		{
			for(int j=1;j<mc;++j)
				scanf("%d",&e[i][j][1]);
			if(i==mr)break;
			for(int j=1;j<=mc;++j)
				scanf("%d",&e[i][j][0]);
		}
		memset(dis,0x7F,sizeof(dis));
		memset(inq,0,sizeof(inq));
		qs=qt=q[0].r=q[0].c=q[0].d=q[0].f=0;
		for(int i=0;i<4;++i)
			if(e[sr+ed[i][0]][sc+ed[i][1]][ed[i][2]])
				addnode(sr+vd[i][0],sc+vd[i][1],i,1,0);
		while(qs!=qt)
		{
			qnode x(q[qs]);
			qs=qs+1&M-1;
			x.dealnode();
		}
		int ans=~0U>>1;
		for(int i=0;i<4;++i)for(int j=0;j<2;++j)
			if(int ce=e[tr+ed[i][0]][tc+ed[i][1]][ed[i][2]])
				if((ce+=ce+dis[tr][tc][i^1][j])<ans)ans=ce;
		if(ans>>30)printf("Case %d: Impossible\n",te);
		else printf("Case %d: %d\n",te,ans);
	}
	return 0;
}