UVA Abbott's Revenge

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
#include <vector>
using namespace std;
struct node
{
int r, c, dir;//横行，竖行及方向
node(int r=0,int c=0,int dir=0):r(r),c(c),dir(dir){}//结构体中定义函数
};
const int maxn = 10;
int has_edge[maxn][maxn][4][3];//判断方向及转向是否可行,用于判断行走的数组
int d[maxn][maxn][4];//记录行走的路径
node p[maxn][maxn][4];//用于记录下个行走的节点
int r0, c0, r1, c1, dir1,r2,c2;
const char* dirs = "NESW";
const char* turns = "FLR";
const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 };//注意四个方向的转向，利用数组控制
int dirid(char c)//该函数作用为将字符在字符串中的数字转换为对应数字，直接利用地址相减
{
return strchr(dirs, c) - dirs;
}
int turnid(char c)//将几种方向转换为相应数字
{
return strchr(turns, c) - turns;
}
bool inside(int r, int c)//判断出界，进行相应转向后，可能造成出界的情况
{
return (r >= 1 && r <= 9 && c >= 1 && c <= 9);
}
node change(const node& u, int turn)//返回结构体，利用循环遍历所有可能情况,对应三种情况，直行，左转，右转
{
int dir = u.dir;
if (turn == 1)//左转
dir = (dir + 3) % 4;//等价逆时针旋转
if (turn == 2)
dir = (dir + 1) % 4;//等价顺时针旋转
return node(u.r + dr[dir], u.c + dc[dir], dir);//返回可能的转向
}
bool read()//读入函数
{
char s1[99], s2[99];
scanf("%s", s1);
if (strcmp(s1, "END") == 0)
return false;
scanf("%d%d%s%d%d", &r0, &c0, s2, &r2, &c2);//读入起点与终点,注意起始点问题,相应状态为刚好离开起点
printf("%sn", s1);
dir1 = dirid(s2[0]);
r1 = r0 + dr[dir1];
c1 = c0 + dc[dir1];//转化起点，起点为离开初始点之后的状态
memset(has_edge, 0, sizeof(has_edge));//has_edge数组用于判断相应转弯方案是否可行
while (1)//读入数据，处理最终可行的方向
{
int r, c;
char s[99];
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][dirid(s[0])][turnid(s[i])] = 1;//记录相应转换方向可行，方便记录路径
}
}
}
return true;
}
void print_f(node u)//输出最后路径
{
vector<node>nodes;
for (;;)//将路径记录至数组中便于最后的输出
{
nodes.push_back(u);//以最后的节点进行回溯寻找,注意细节，先保存再判断，保证存入题中要求的起始状态
if (d[u.r][u.c][u.dir] == 0)//找到起始点，结束循环
break;
u = p[u.r][u.c][u.dir];//p保留父节点，利用p数组进行回溯
}//最后输出时直接进行倒序输出
nodes.push_back(node(r0, c0, dir1));
int count = 0;//count用于格式控制，注意相应格式控制的细节
for (int i = nodes.size() - 1; i >= 0; i--)
{
if (count % 10 == 0)//10个一组,注意起始有空格
printf(" ");
printf(" (%d,%d)", nodes[i].r, nodes[i].c);
if (++count % 10 == 0)
printf("n");
}
if (nodes.size() % 10 != 0)//不是所有的行的情况都是10的整数倍，细节格式
printf("n");
}
void solve()//利用bfs不断递归寻找可能出口
{
queue<node>q;//利用队列不断寻找出口
memset(d, -1, sizeof(d));//注意初始化起始点，控制条件的结束
node u(r1, c1, dir1);//以起始点进行深度搜索
d[u.r][u.c][u.dir] = 0;
q.push(u);
while (!q.empty())
{
node u = q.front(); q.pop();
if (u.r == r2 && u.c == c2)//找到终点，输出结果，返回，注意寻找结束点的控制
{
print_f(u);
return;
}
for (int i = 0; i < 3; i++)//用循环遍历可能的方向及转向,i控制旋转的方向
{
node v = change(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记录可能的行走路径
{
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())
{
solve();
}
getchar();
getchar();
return 0;
}

8、注意has_edge数组的检索，应该是判断未转向之前是否存在相应的状态，易错点，注意理解has_edge数组的作用

最后

以上就是苹果战斗机为你收集整理的UVA Abbott's Revenge的全部内容，希望文章能够帮你解决UVA Abbott's Revenge所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。