UVA 10047-The Monocycle(队列bfs 保存4种状态）

题意：给你一张地图，S代表起点，T代表终点，有一个轮盘，轮盘平均分成5份，每往前走一格恰好转1/5，轮盘只能往前进，但可以向左右转90°，每走一步或是向左向右转90°

要花费1单位的时间，问最少的时间到达终点，如果无法到达，输出 destination not reachable,起点状态是朝北，着地颜色是绿色，到达终点的条件是着地颜色是绿色，方向任意。

解析：bfs搜一遍，但要保存4种状态，分别是坐标x,y,方向和颜色。每次选择有3种，1、向前进，2、左转，3、右转。

代码如下：

#include
#include
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int INF=1000000007; const double eps=0.00000001; const int maxn=26; int row,col,bex,bey,ans; //bex,bey是起点坐标 string maze[maxn]; //0:north,1:west,2:south,3:east bool vis[maxn][maxn][4][5]; //green:0,black:1,red:2,blue:3,white:4 bool in(int x,int y){ return x>=0&&x&&y>=0&&y; } //是否在地图内 struct node // 保存4种状态以及花费 { int x,y,dir,color; int dist; node(int x=0,int y=0,int dir=0,int color=0,int dist=0) :x(x),y(y),dir(dir),color(color),dist(dist){} }; queue que; void init() { while(!que.empty()) que.pop(); memset(vis,0,sizeof(vis)); } void addnode(int x,int y,int dir,int color,int dist) // 增加节点 { if(in(x,y)&&maze[x][y]!='#'&&!vis[x][y][dir][color]) // 在地图内，不是墙，且该种状态未被访问过 { vis[x][y][dir][color]=true; que.push(node(x,y,dir,color,dist)); } } void same_dir(int x,int y,int dir,int color,int dist) // 向前进 { if(dir==0) addnode(x-1,y,dir,(color+1)%5,dist+1); //颜色要变化 else if

转载于:https://www.cnblogs.com/wust-ouyangli/p/4742271.html

本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 162202241@qq.com 举报，一经查实，本站将立刻删除。

1313e

UVA 10047-The Monocycle(队列bfs 保存4种状态）

取消回复欢迎您发表评论:

默认分类  Docker中运行Nodejs和Webpack若干问题的解决

默认分类  JVM你必须知道的那些事儿

默认分类  WPF字体图标——IconFont

默认分类  内核中修改和保存defconfig的方法

默认分类  JetCache快速入门

1313e

UVA 10047-The Monocycle(队列bfs 保存4种状态）

取消回复欢迎您发表评论:

默认分类 Docker中运行Nodejs和Webpack若干问题的解决

默认分类 JVM你必须知道的那些事儿

默认分类 WPF字体图标——IconFont

默认分类 内核中修改和保存defconfig的方法

默认分类 JetCache快速入门

默认分类内核中修改和保存defconfig的方法