Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

给点数据啊 我wa疯了

Posted by qqmsyz5200 at 2009-05-05 14:49:30 on Problem 1475
# include <iostream>
# define check(xx,yy) (xx>0&&yy>0&&xx<=m&&yy<=n)
using namespace std;
const int MAXN=21;
const int move[][2]={{-1,0},{1,0},{0,-1},{0,1}}; //N S W E
const char M[5]="NSWE";
int op[4][4];
char mate[MAXN][MAXN];
int m,n;
int bx,by , tax,tay , rx,ry;  //the init of box ,ren and Target
int ansb[10000][3], ansr[10000],  ans[10000];
bool vb[MAXN][MAXN] , vr[MAXN][MAXN];
struct queue{
	int pre;         //qian
	char rx,ry;
	char x,y;
}qu[10000000];
int qr[1000000][3];  //0,1-x,y 2-pre
int bfsr(int rrx,int rry,int edx,int edy)
{
	if(!(check(edx,edy))) return -1;
	int e=1,h=0,i,tx,ty;
	memset(vr,0,sizeof(vr));
	qr[e][0]=rrx,qr[e][1]=rry;
	qr[e][2]=-1;
	while(e-h)
	{
		h++;
		for(i=0;i<4;i++)
		{
			tx=qr[h][0]+move[i][0],ty=qr[h][1]+move[i][1];
			if(check(tx,ty) && !vr[tx][ty] && mate[tx][ty]!='#') //r exp_node
			{
				++e;
				qr[e][0]=tx,qr[e][1]=ty;
				qr[e][2]=h;
				vr[tx][ty]=1;
				if(tx==edx && ty==edy) return e;
			}
		}
	}
	return -1;
}

int bfs()
{
	int e=1,h=0,i,tx,ty,a,ex,ey;
	qu[e].pre=-1;
	qu[e].rx=rx,qu[e].ry=ry;
	qu[e].x =bx,qu[e].y =by;
	memset(vb,false,sizeof(vb));
	vb[bx][by]=true;
	while(e-h)
	{
		h++;
		for(i=0;i<4;i++)
		{
			tx=qu[h].x+move[i][0],ty=qu[h].y+move[i][1];
			if(check(tx,ty) && !vb[tx][ty] && mate[tx][ty]!='#')
			{
				ex=qu[h].x-move[i][0],ey=qu[h].y-move[i][1];
				a=1;
				mate[ qu[h].x  ][  qu[h].y ]='#';
				if(!(qu[h].rx==ex && qu[h].ry==ey)) a=bfsr(qu[h].rx,qu[h].ry,ex,ey);
				mate[ qu[h].x  ][  qu[h].y ]='.';
				if(a+1)	//player can reach than exp_node
				{
					++e;
					qu[e].pre=h,qu[e].x=tx,qu[e].y=ty;
					qu[e].rx=qu[h].x,qu[e].ry=qu[h].ry;
					vb[tx][ty]=1;
					if(tx==tax&&ty==tay) return e;
				}
			}
		}
	}
	return -1;
}

void solve()
{
	int i,j,a,k,kk,ak=0,ex,ey,t;
	memset(mate,0,sizeof(mate));
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			cin>>mate[i][j];
			switch(mate[i][j])
			{
				case 'B': bx=i,by=j;break;
				case 'T': tax=i,tay=j;break;
				case 'S': rx=i,ry=j;break;
			}
		}
	}
	k=0;
	a=bfs();
	if(a==-1){puts("Impossible.");return;}
	while(qu[a].pre!=-1)
	{
		t=qu[a].pre;
		ansb[++k][0]=op[ qu[a].x - qu[t].x +1 ][  qu[a].y - qu[t].y +1   ];
		ansb[k][1]=a,ansb[k][2]=t;
		a=t;
	}
	for(i=k;i>0;i--)
	{
		mate[qu[ansb[i][2]].x  ][qu[ansb[i][2]].y]='#';
		ex=qu[ansb[i][2]].x - move[ansb[i][0] ][0],ey=qu[  ansb[i][2] ].y -  move[ansb[i][0] ][1];
		if(ex==rx&&ey==ry) goto aaa;
		a=bfsr( rx,ry,ex  , ey);
		if(a==-1){puts("Impossible.");return;}
		kk=0;
		while(qr[a][2]!=-1)
		{
			t=qr[a][2];
			ansr[++kk]=M[op[ qr[a][0] - qr[t][0] +1   ][  qr[a][1] -qr[t][1]+1  ]]+32;
			a=t;
		}
		for(j=kk;j>=1;j--)
		{
			ans[++ak]=ansr[j];
		}
aaa:	ans[++ak]=M[ansb[i][0]];
		mate[qu[ansb[i][2]].x  ][qu[ansb[i][2]].y]='.';
		rx=ex+move[ ansb[i][0] ][0],ry=ey+move[ansb[i][0]][1];
	}
	for(i=1;i<=ak;i++)putchar(ans[i]);
	putchar(10);
}

int main()
{
	int T=0,i;
	for(i=0;i<4;i++)
	{
		op[ move[i][0]+1 ][ move[i][1]+1 ] = i;
	}
	while(cin>>m>>n ,m&&n)
	{
		printf("Maze #%d\n",++T);
		solve();
		putchar(10);
	}
	return 0;
}

不晓得怎么的 一直wa wa的
dis里面的数据都过了的

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator