首页 > 代码库 > 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 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。