UVA Abbott's Revenge

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#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;
}