首页 > 代码库 > UVa10047 BFS

UVa10047 BFS

题意:一自行车的轮子被分成5个扇区,涂了5种不同颜色。自行车每1秒要么骑到下一个格子,要么左转或者右转90。一开始自行车面向北,颜色为绿,到达目标格时,必须触底颜色为绿,但朝向无限制。求到达目标格的最短时间。

思路:可以朝3个方向搜索,多了一种颜色状态,每个结点有四个值需要保存,坐标x,坐标y,朝向,底面颜色。每个结点只可以执行一次,不然会出现死循环。所以需要vis数组标记。

代码:

#include<cstdio>#include<cstring>#include<queue>#include<algorithm>const int maxn = 30;struct node{	int x,y,s,c,dis;//x,y是坐标 s是方向 c是颜色 dis是距离	node(int x = 0,int y = 0,int s = 0,int c = 0,int dis = 0):x(x),y(y),s(s),c(c),dis(dis){}	bool operator < (const node &a) const	{		return a.dis < dis;	}};char map[maxn][maxn];int vis[maxn][maxn][4][5];int n,m;int d[4][2] = {-1,0,0,1,1,0,0,-1};std::priority_queue<node> q;int BFS(int sx,int sy,int ex,int ey){	q.push(node(sx,sy,0,0,0));	vis[sx][sy][0][0];	node pp;	while(!q.empty())	{		pp =q.top(); 		q.pop();		if(pp.x == ex && pp.y == ey && pp.c == 0)		{			return pp.dis;		}		for(int i=0;i<4;i++)		{			int dx = pp.x + d[i][0];			int dy = pp.y + d[i][1];			int dis = pp.dis+1;			int c = (pp.c+1)%5;						if(i == pp.s)			{				if(dx >= n || dx < 0 || dy < 0 || dy >= m)continue;				if(map[dx][dy] == ‘#‘ || vis[dx][dy][pp.s][c]) continue;				q.push(node(dx,dy,i,c,dis));				vis[dx][dy][pp.s][c] = 1;			}else			{				if((pp.s+1)%4 == i || (pp.s-1+4)%4 == i)				{					if(vis[pp.x][pp.y][i][pp.c])continue;					vis[pp.x][pp.y][i][pp.c] = 1;					q.push(node(pp.x,pp.y,i,pp.c,dis));				}			}		}	}	return -1;}int main(){	int i,j;	int sx,sy,ex,ey;	int cas = 1;	while(scanf("%d%d",&n,&m),n+m)	{		while(!q.empty())q.pop();		memset(vis,0,sizeof(vis));		for(i=0;i<n;i++)		{			scanf("%s",map[i]);			for(j=0;j<m;j++)			{				if(map[i][j] == ‘S‘)					sx = i, sy = j;				if(map[i][j] == ‘T‘)					ex = i, ey = j;			}		}		if(cas > 1) printf("\n");		printf("Case #%d\n",cas++);		int ans = BFS(sx,sy,ex,ey);		if(ans == -1) printf("destination not reachable\n");		else printf("minimum time = %d sec\n",ans);	}	return 0;}/*1 3S#T10 10#S.......##..#.##.###.##.##.##.#....##.###.##..#.##..#.##...#......##...##.##...#.###...#.#.....###T0 0  */