现在的位置: 首页 > 综合 > 正文

pku1376Robot

2013年12月11日 ⁄ 综合 ⁄ 共 3714字 ⁄ 字号 评论关闭

   这题主要经典的广搜,一般方法定义一个数组表示每个位置的四个面是否被访问,然后用队列来做就可以了!只是要注意下旁边是不能走的!代码如下(参照别人的,结构很清晰!)

/*Problem: 1376  User: qjklw 
Memory: 208K  Time: 94MS 
Language: C++  Result: Accepted 
*/
#include <iostream>
#include <queue>
using namespace std;

#define maxint 51
struct Point                  
{ 
	int x, y, length, face;
	Point(int x1, int y1, int length1, int face1)
	{
		x=x1;      
		y=y1;
		length=length1;                     
		face=face1;
	}
};
int g[maxint][maxint];
int v1x, v2x, v1y, v2y, ori, M, N;                     
int position[4][2]={{0,1}, {1,0}, {0,-1}, {-1, 0}} ;
bool visit[maxint][maxint][4];

void input()
{
    int i, j, k ;
	char a[10] ;
	 
	for(i=0; i<M; i++)
		for(j=0; j<N; j++)
			scanf("%d",&g[i][j]) ;

	for(i=0; i<M; i++)
		for(j=0; j<N; j++)
			for(k=0; k<4; k++)
				visit[i][j][k]=false;
    
	scanf("%d%d%d%d", &v1x, &v1y, &v2x, &v2y) ;
	v1x--, v2x--, v1y--,  v2y--;

    scanf("%s",a) ;
	if(!strcmp(a,"south"))       ori=1 ;
	else if(!strcmp(a,"east"))   ori=0 ;     
	else if(!strcmp(a,"west"))   ori=2 ;
	else                         ori=3 ;
}

void solve()
{
	queue<Point> q;
	Point p(v1x, v1y, 0, ori);
	q.push(p) ;

    int Length=-1, tx, ty, i, tlength, tface ;
	while(!q.empty())
	{
		Point top=q.front();
		if(top.x==v2x&&top.y==v2y)
		{
			Length=top.length;
			break;
		}

        tx=top.x;
		ty=top.y;
		tlength=top.length;
		for(i=-1; i<=1; i+=2)
		{
			tface=(top.face+i+4)%4 ;
			if(visit[tx][ty][tface])
				continue;
			Point tp(tx, ty, tlength+1, tface) ;
			q.push(tp) ;
			visit[tx][ty][tface]=true ;
		}

		tface=top.face;
		tlength=top.length;
		for(i=1; i<=3; i++)
		{
			tx=top.x+i*position[tface][0];
			ty=top.y+i*position[tface][1];
			if(visit[tx][ty][tface])
				continue;
			if(tx<0||tx>=M-1||ty<0||ty>=N-1 || g[tx][ty]||g[tx+1][ty]||g[tx][ty+1]||g[tx+1][ty+1])
				break;
			Point tp(tx, ty, tlength+1, tface);
			q.push(tp);
			visit[tx][ty][tface]=true;
		}

		q.pop();
	}

	printf("%d\n", Length) ;
}
int main()
{
	while(scanf("%d%d", &M, &N))
	{
		if(!M&&!N)   break ;

		input() ;
		solve() ;
	}
	return 0;
}

 方法二、直接把满足题意的点加入队列,只有第一个点向后转才有意义,其余的点向后转浪费。这种方法队列很容易溢出,我wa了好多次,查了好多时间,最后就是在跳的下一个点的要求上弄严格了(只有下一个点没跳到过或是经过相同的步数到达但方向不同的时候才加入队列),就过了。

/*Source Code

Problem: 1376  User: qjklw 
Memory: 324K  Time: 32MS 
Language: C++  Result: Accepted 
*/
#include <iostream>
using namespace std ;

const int maxint=10000;
struct Vertex
{
	int x, y, length, face ;
}vertex[maxint] ;

int graph[51][51] ;
int way[4][3][2]={ {{0,1},{0,2},{0,3}}, {{1,0},{2,0},{3,0}}, {{0,-1},{0,-2},{0,-3}}, {{-1,0},{-2,0},{-3,0}}} ;

int M, N, v1x, v2x, v1y, v2y, ori ;
void input()
{
	int i, j ;
	char a[10] ;
	 
	for(i=0; i<M; i++)
		for(j=0; j<N; j++)
			scanf("%d",&graph[i][j]) ;
    
	scanf("%d%d%d%d", &v1x, &v1y, &v2x, &v2y) ;
	v1x--, v2x--, v1y--,  v2y--;

    scanf("%s",a) ;
	if(!strcmp(a,"south"))       ori=1 ;
	else if(!strcmp(a,"east"))   ori=0 ;     
	else if(!strcmp(a,"west"))   ori=2 ;
	else                         ori=3 ;
}

void solve()
{
	int head=0, tail=0, i, k, m, n, p, flag=0;

    if(v1x==v2x && v1y==v2y)
	{              
		printf("0\n") ;
		return ;
	}
	                           
	vertex[head].x=v1x;                               
	vertex[head].y=v1y;
	vertex[head].face=ori;
	vertex[head++].length=0;

	while(head!=tail)
	{
		k=tail;
		tail=(tail+1)%maxint; 

		for(i=0;i<3;i++)
		{
			m = vertex[k].x+way[vertex[k].face][i][0] ;                                 
			n = vertex[k].y+way[vertex[k].face][i][1] ;
			p = vertex[k].length ;
			if(graph[m+1][n]!=1||graph[m][n+1]!=1||graph[m+1][n+1]!=1|| m<M-1||m>=0 || n<N-1||n>=0)
				break;
			if(!graph[m][n]||(graph[m][n]==p+1&&graph[m][n]!=1))//此顶点没到过或以相同的步数,不同的方向到
			{ 
				if(m==v2x && n==v2y)             
				{
					printf("%d\n", p+1) ;
					return;
				}
                 
				vertex[head].x=m;
				vertex[head].y=n;
				vertex[head].length=p+1;
				vertex[head].face=vertex[k].face;

				head=(head+1)%maxint;
			}
			else
				break ;
		}

		if(!graph[vertex[k].x][vertex[k].y])
		{
			vertex[head].x=vertex[k].x; //向右转
		    vertex[head].y=vertex[k].y;
		    vertex[head].length=vertex[k].length+1;
		    vertex[head].face=(vertex[k].face+1)%4;
		    head=(head+1)%maxint;
 
            vertex[head].x=vertex[k].x; //向左转
		    vertex[head].y=vertex[k].y;
		    vertex[head].length=vertex[k].length+1;
		    vertex[head].face=(vertex[k].face+3)%4;
		    head=(head+1)%maxint;
            
			if(!flag)//起点可以经过同一方向转两次至相反方向(往后转).其余点往后转没意义            
			{
			     flag=1;
                 vertex[head].x=vertex[k].x;
		         vertex[head].y=vertex[k].y;
		         vertex[head].length=vertex[k].length+2;   
		         vertex[head].face=(vertex[k].face+2)%4;                 
		         head=(head+1)%maxint;

				 graph[vertex[k].x][vertex[k].y]=2;
				 continue;
			}

			  graph[vertex[k].x][vertex[k].y]=vertex[k].length+1;
		}
	
	}

	printf("-1\n") ;           
}
int main()                  
{
	while(scanf("%d%d", &M, &N))
	{
		if(!M&&!N)   break ;

		input() ;
		solve() ;
	}
	return 0 ;
}

 

抱歉!评论已关闭.