poj 2935 (bfs+路径)

题目链接：http://poj.org/problem?id=2935

 

解题报告：刷到bfs明显的感觉有些难，这道题应该卡的有3~4天了吧！

首先说明一下bfs如何记录路径：在结构体中，用一个值来记录上一个的位置，然后再“回溯”（并不是真的回溯）到第一个元素，然后递归输出即可；

第二点：交换两个数的位运算方法：a^=b^=a^=b,看上去显得代码更有技术含量

第三点：注意输入值的顺序，我就在这卡了n久

 

#include<cstdio>
#include<cstring>
#include<queue>
#define swap(a,b) a^=b^=a^=b 
using namespace std;

const int maxn = 15;
const int dir[4][2]={0,2,2,0,0,-2,-2,0};
const char ch[4]={'E','S','W','N'};

struct node 
{
	int x,y;
	int pre;
	char c;
}q[maxn*maxn];

int sx,sy,ex,ey,num;
int mp[maxn][maxn];		

bool iswall( int x,int y,int i)
{
	if ( i==0 && mp[x][y-1] ) return true;
	else if(i==1&&mp[x-1][y]) return true;
	else if(i==2&&mp[x][y+1]) return true;
	else if(i==3&&mp[x+1][y]) return true;
	else return false;
}

void print(int x)
{
	if(x) 
	{
		print(q[x].pre );
		printf("%c",q[x].c);
	}
}

void bfs( )
{
	int front = 0, rear =  0;
	node frm = {sx,sy,0,0};
	q[rear++] = frm;
	while(front < rear)
	{
		frm = q[front];
		for( int i=0;i<4;i++)
		{
			node to = {frm.x+dir[i][0],frm.y+dir[i][1],front,ch[i]};
			if(to.x < 2||to.x >12||to.y <2||to.y > 12) continue;
			if(!mp[to.x][to.y]&&!iswall(to.x,to.y,i))
			{
				mp[to.x][to.y] = 1; 
				q[rear] = to;
				if(to.x==ex&&to.y==ey) 
				{
					print( rear );//printf("\nrear = %d front = %d",rear,front);
					return ;
				}
				++rear;
			}
		}
		++front;
	} 
}

int main()
{
	int a1,a2,b1,b2;
	while(scanf("%d%d",&sy,&sx)&&(sx||sy))
	{
		scanf("%d%d",&ey,&ex);
		memset(mp,0,sizeof(mp));
		ex = 2*ex;ey = 2*ey;
		sx = 2*sx;sy = 2*sy;
		mp[sx][sy] = 1;
		for(int i=0;i<3;i++)
		{
			scanf("%d%d%d%d",&b1,&a1,&b2,&a2);
			if( a1 == a2 )
			{
				if(b1>b2) swap(b1,b2);
				for(int j=b1;j<b2;j++)
					mp[a1*2+1][j*2+2]=1;
			}
			else 
			{
				if(a1>a2) swap(a1,a2);
				for(int j=a1;j<a2;j++)
					mp[2*j+2][b1*2+1]=1;
			}
		}	
		if( sx==ex && sy ==ey )
		{
			puts("");
			continue;
		}  
		bfs();
		printf("\n");
		
	}
	return 0;
}