1. 首页
  2. 文章中心
  3. ACM

Uva oj 816 Abbott Revenge（BFS最短路）

87 阅读 0 评论
我是靠谱客的博主 从容芝麻，这篇文章主要介绍Uva oj 816 Abbott Revenge（BFS最短路），现在分享给大家，希望可以做个参考。

  • 原题链接：Here！

  • 闲话：看到题目的时候还是很懵的，这个迷宫很特殊，特殊的地方在对于每一个点都多出来一些要求，比如进入一个交叉点的"朝向"( NESW，北东南西 )是不同的，对应不同的"朝向"，出去的方向也是不尽相同的。好吧，根本没有思路，真不愧是Final的题。
  • 部分变量设置：
    1. (r,c) 代表点的坐标，特殊的(r0,c0)代表Enterance，(r2,c2)代表Goal，(r1,c1)代表起始点
    2. dir   代表朝向，朝向有4个“N，E，S，W”，顺时针
    3. turn  代表转向方向，F直走，L左转，R右转
    4. d[r][c][dir] 代表起始点到点(r,c,dir)的最短长度
    5. p[r][c][dir] 代表点(r,c,dir)在BFS树上的父点
    6. has_edge[r][c][dir][turn] 判断是否可以转向
    7. dr[],dc[],struct Node{}的解释都在下面

  • 分析：现在回过头来看它与普通迷宫题在本质上是一样的，只不过是多出了一些条件。因为现在对于每一个点都会有三个状态，行r，列c，以及进入的方向dir，所以使用三元数组(r,c,dir)来表示状态“位于点(r,c)，朝向dir”。需要注意的是起点并不是(r0,c0)，题目中描述的是在规定的入口方向进入，所以开始的点应该是(r1,c1)，d[r][c][dir] 代表起始点到点(r,c,dir)的最短长度，p[r][c][dir] 代表点(r,c,dir)在BFS树上的父点。对于任意一个状态 U(r,c,dir) 和 其后继状态 V(r',c',dir')，如果在能够转向( has_edge[r][c][dir][turn]==1 )，后继点V(r,c)在图里且还没被遍历过，就将后继状态V加入到vector中，然后更新状态V最短长度和V的父结点。如果在BFS扩增中能够到达Goal，跳出循环返回ture，如果循环结束还没有找到Goal，返回false。

  • 实现：

    1.输入部分
    将4个方向N E S W 和 3个转向F L R 转换成数字0~3和0~2，这样可以简化问题。这技巧真很强，厉害。
    复制代码
    1
    2
    3
    4
    5
    6
    7
    const char* dirs = "NESW";
// 顺时针旋转
const char* turns = "FLR";
// 转弯方式 F直走，L左转，R右转
const int dr[] = {-1, 0, 1,
0};// 将4个方向和3种"转弯方式"编号为0~3和0~2	转弯方式：直走，左转，右转
const int dc[] = { 0, 1, 0, -1};
    复制代码
    1
    2
    3
    4
    5
    6
    //
转换函数,将字符转换成数字
int dir_id(char c) {	return strchr(dirs,c)-dirs; }
// 用法独特真的很强
int turn_id(char c){
return strchr(turns,c)-turns; }
    技巧balabala:先用字符指针指向了一个字符串常量，然后strchr(dirs,c)会返回字符c在字符串中第一次出现位置的指针，然后用 返回值 — 指向字符串的指针，就能得到字符c在字符串dirs中的"位置"了。厉害word刘。
     
    复制代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    bool read_case(){
char s[99],s2[99];
scanf("%s",s);
if(s[0]=='E')	return false;
if(scanf("%d%d%s%d%d",&r0,&c0,s2,&r2,&c2)!=5) return false;	// 录入起点和终点信息
printf("%sn",s);
dir=dir_id(s2[0]);
r1=r0+dr[dir];
c1=c0+dc[dir];
//除了1、2行特殊处理之外
//对于其他行，首先输入(r,c)然后输入一些指令，指令个数和长度不确定
memset(has_edge,0,sizeof(has_edge));
while(1){
int r,c;
scanf("%d",&r);
if(r==0)	break;
scanf("%d",&c);
// 指令以*结束，指令第一个字符代表朝向，其他字符代表可转向的方向
while(scanf("%s",s)==1 && s[0]!='*'){
for(int i=1;i<strlen(s);i++)
has_edge[r][c][dir_id(s[0])][turn_id(s[i])]=1;
}
}
return true;
}

    2.输出部分
    复制代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void print_ans(Node u){
//倒序存放到vector中
vector<Node> nodes;
while(1){
nodes.push_back(u);
if(d[u.r][u.c][u.dir]==0)	break;
u=p[u.r][u.c][u.dir];
}
nodes.push_back(Node(r0,c0,dir));
// 每行10个，注意每行开头有两个空格
int cnt=0;
for(int i=nodes.size()-1;i>=0;i--){
if(cnt%10==0)	printf(" ");
printf(" (%d,%d)",nodes[i].r,nodes[i].c);
if(++cnt%10==0)	printf("n");
}
if(nodes.size()%10!=0)	printf("n");
}

    3.最重要的部分
    对于任意一个状态 U(r,c,dir) 和 其后继状态 V(r',c',dir')，如果在能够转向( has_edge[r][c][dir][turn]==1 )，后继点V(r,c)在图里且还没被遍历过，就将后继状态V加入到vector中，然后更新状态V最短长度和V的父结点。如果在BFS扩增中能够到达Goal，跳出循环返回ture，如果循环结束还没有找到Goal，返回false。

    在分析里有一个很关键的问题，如果找到后继状态？
    复制代码
    1
    2
    3
    4
    5
    6
    7
    // 接下来是"行走"函数，根据当前的状态和转弯方式，计算出后继状态
Node walk(const Node& u,int turn){
int dir = u.dir;
if(turn==1)	dir=(dir + 3) % 4;	// 左转，逆时针-1，但是不能出现负数，所以+3 %4
if(turn==2)	dir=(dir + 1) % 4;	// 右转，顺时针+1
return Node(u.r+dr[dir],u.c+dc[dir],dir);	// 返回后继状态
}

    判断点V在图里
    复制代码
    1
    2
    3
    4
    bool inside(int r,int c){
// 判断是否在Maze里面
return (r>=1 && r<MAX && c>=1 && c<MAX);
}

    BFS
    复制代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void BFS(){
queue<Node>	q;
memset(d,-1,sizeof(d));
Node u(r1,c1,dir);
d[u.r][u.c][u.dir]=0;
// 第一个点在BFS树上的父亲自然是 0
q.push(u);
while(!q.empty()){
Node u=q.front();	q.pop();
if(u.r==r2 && u.c==c2){ print_ans(u); return; }
for(int i=0;i<3;i++){	// 四个方向进行遍历
Node v=walk(u,i);	// v代表u向方向i走的一个后继节点
if(has_edge[u.r][u.c][u.dir][i] && inside(v.r,v.c) && d[v.r][v.c][v.dir]<0){
d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1;
p[v.r][v.c][v.dir]=u;
q.push(v);
}
}
}
printf("
No Solution Possiblen");
}

  • CODE
    复制代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    #include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX = 10;
const char* dirs = "NESW";
// 顺时针旋转
const char* turns = "FLR";
// 转弯方式 F直走，L左转，R右转
const int dr[] = {-1, 0, 1,
0};// 将4个方向和3种"转弯方式"编号为0~3和0~2	转弯方式：直走，左转，右转
const int dc[] = { 0, 1, 0, -1};
struct Node{
int dir,r,c;
Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir) {}	//构造函数
};
int r0,c0,dir,r1,c1,r2,c2;
// r0,c0 起点坐标 r2,c2 终点坐标
int has_edge[MAX][MAX][4][3];	// has_edge[r][c][dir][turn],四元数组，记录点(r,c)的朝向 和 可以选择的方向
int d[MAX][MAX][4];
Node p[MAX][MAX][4];
//
转换函数,将字符转换成数字
int dir_id(char c) {	return strchr(dirs,c)-dirs; }
// 用法独特真的很强
int turn_id(char c){
return strchr(turns,c)-turns; }
// 输入部分
bool read_case(){
char s[99],s2[99];
scanf("%s",s);
if(s[0]=='E')	return false;
if(scanf("%d%d%s%d%d",&r0,&c0,s2,&r2,&c2)!=5) return false;	// 录入起点和终点信息
printf("%sn",s);
dir=dir_id(s2[0]);
r1=r0+dr[dir];
c1=c0+dc[dir];
//除了1、2行特殊处理之外
//对于其他行，首先输入(r,c)然后输入一些指令，指令个数和长度不确定
memset(has_edge,0,sizeof(has_edge));
while(1){
int r,c;
scanf("%d",&r);
if(r==0)	break;
scanf("%d",&c);
// 指令以*结束，指令第一个字符代表朝向，其他字符代表可转向的方向
while(scanf("%s",s)==1 && s[0]!='*'){
for(int i=1;i<strlen(s);i++)
has_edge[r][c][dir_id(s[0])][turn_id(s[i])]=1;
}
}
return true;
}
// 接下来是"行走"函数，根据当前的状态和转弯方式，计算出后继状态
Node walk(const Node& u,int turn){
int dir = u.dir;
if(turn==1)	dir=(dir + 3) % 4;	// 左转，逆时针-1，但是不能出现负数，所以+3 %4
if(turn==2)	dir=(dir + 1) % 4;	// 右转，顺时针+1
return Node(u.r+dr[dir],u.c+dc[dir],dir);	// 返回后继状态
}
bool inside(int r,int c){
// 判断是否在Maze里面
return (r>=1 && r<MAX && c>=1 && c<MAX);
}
void print_ans(Node u){
//倒序存放到vector中
vector<Node> nodes;
while(1){
nodes.push_back(u);
if(d[u.r][u.c][u.dir]==0)	break;
u=p[u.r][u.c][u.dir];
}
nodes.push_back(Node(r0,c0,dir));
// 打印解，每行10个,
int cnt=0;
for(int i=nodes.size()-1;i>=0;i--){
if(cnt%10==0)	printf(" ");
printf(" (%d,%d)",nodes[i].r,nodes[i].c);
if(++cnt%10==0)	printf("n");
}
if(nodes.size()%10!=0)	printf("n");
}
void BFS(){
queue<Node>	q;
memset(d,-1,sizeof(d));
Node u(r1,c1,dir);
d[u.r][u.c][u.dir]=0;
// 第一个点在BFS树上的父亲自然是 0
q.push(u);
while(!q.empty()){
Node u=q.front();	q.pop();
if(u.r==r2 && u.c==c2){ print_ans(u); return; }
for(int i=0;i<3;i++){	// 四个方向进行遍历
Node v=walk(u,i);	// v代表u向方向i走的一个后继节点
if(has_edge[u.r][u.c][u.dir][i] && inside(v.r,v.c) && d[v.r][v.c][v.dir]<0){
d[v.r][v.c][v.dir]=d[u.r][u.c][u.dir]+1;
p[v.r][v.c][v.dir]=u;
q.push(v);
}
}
}
printf("
No Solution Possiblen");
}
int main(){
while(read_case()){
BFS();
}
return 0;
}

  • 收获最大的是如果在遇到相同问题，明白"结点"包含哪些内容是很重要的。可以用多元数组描述一个多个参数的状态，在用数字代替字符"NESW"时也很精彩，walk()函数中找后继状态也很精彩。

  • Think：优秀的代码里透露出一种美，简直不可名状，恰好听到Unbelievable--Owl City/Hanson，Oh~我突然找到了发现新奇小玩具的那种快乐~~~  Unbelievable,You haven’t seen nothing yet,I'm so amazed, those were the days.




最后

以上就是从容芝麻最近收集整理的关于Uva oj 816 Abbott Revenge（BFS最短路）的全部内容，更多相关Uva内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(58)

相关文章

Abbott的复仇(Abbott's Revenge)
Abbott的复仇(Abbott's Revenge)
2.BFS宽度优先搜索（模板）1.走迷宫2.八数码
2.BFS宽度优先搜索（模板）1.走迷宫2.八数码
UVA Abbott's Revenge
UVA Abbott's Revenge
UVA 1595 Symmetry(对称轴)
UVA 1595 Symmetry(对称轴)
Uva oj 816 Abbott Revenge（BFS最短路）
Uva oj 816 Abbott Revenge（BFS最短路）
UVA - 816 Abbott's Revenge（bfs）
UVA - 816 Abbott's Revenge（bfs）
J - Abbott's Revenge 搜索 寒假训练
J - Abbott's Revenge 搜索 寒假训练
uva 816 Abbott's Revenge （走迷宫BFS）
uva 816 Abbott's Revenge （走迷宫BFS）

评论列表共有 0 条评论

立即
投稿
返回
顶部