4795456_mle.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int ma[25][25];
int w,h;
int sx,sy,ex,ey;
int xm[4]={0,0,-1,1};
int ym[4]={1,-1,0,0};
bool used[25][25];
struct point
{
	int x,y,step;
	int map[25][25];
}q[35000];
point getnext(point ne,int dir)
{
	int gx=ne.x;
	int gy=ne.y;
	while(ne.x>=0&&ne.x<=h-1&&ne.y>=0&&ne.y<=w-1)
	{
		switch(ne.map[ne.x][ne.y]) 
		{
		case 2:
		case 0:ne.x+=xm[dir];ne.y+=ym[dir];break;
		case 1:
			ne.map[ne.x][ne.y]=0;
			ne.x-=xm[dir];ne.y-=ym[dir];
			if(ne.x==gx&&ne.y==gy) {ne.x=h;return ne;}
			else {ne.step++;return ne;}
		case 3:return ne;
		}
	}
	return ne;
}
bool bfs()
{
	int ql=0,i,j;
	q[0].x=sx;q[0].y=sy;q[0].step=0;
	for(i=0;i<h;i++)
		for(j=0;j<w;j++)
			q[0].map[i][j]=ma[i][j];
	memset(used,false,sizeof(used));
	int head=0,tail=1;
	while(head<tail)
	{
		point t=q[head];
		if(t.step>=10) return false;
		for(int count=0;count<4;count++)
		{
			point ne;
			ne=getnext(t,count);
			if(ne.x==ex&&ne.y==ey) {cout<<ne.step+1<<endl;return true;}
			else
				if(ne.x>=0&&ne.x<=h-1&&ne.y>=0&&ne.y<=w-1)
				{
					q[tail]=ne;
					tail++;
				}
		}
		head++;
	}
	return false;
}
int main()
{
	while(scanf("%d%d",&w,&h))
	{
		if(w==0&&h==0) return 0;
		int i,j;
		for(i=0;i<h;i++)
		{
			for(j=0;j<w;j++) 
			{
				cin>>ma[i][j];
				switch(ma[i][j])
				{
				case 2:sx=i;sy=j;break;
				case 3:ex=i;ey=j;break;
				}
			}
		}
		if(!bfs()) cout<<-1<<endl;
	}
	return 0;
}