【例题 6-14 UVA-816】Abbott's Revenge

90 阅读 0 评论 60 点赞

我是靠谱客的博主健壮期待，这篇文章主要介绍【例题 6-14 UVA-816】Abbott's Revenge，现在分享给大家，希望可以做个参考。

【链接】我是链接,点我呀:)
【题意】

在这里输入题意

【题解】

预处理出某个方向的左边、前边、右边是哪个方向就好了。
然后就是普通的bfs了。
hash存到某个点,走到这里的方向的最小距离。
dfs输出路径。

【代码】

复制代码

#include <bits/stdc++.h>
using namespace std;
//[where in,point]minimum dis
//0 up 1 down 2 left 3 right
const int dx[4] = { -1,1,0,0 };
const int dy[4] = { 0,0,-1,1 };
const int N = 9;
const int INF = 0x3f3f3f3f;
struct abc {
int dir, x, y;
};
int bo[N + 5][N + 5][4], xx1, yy1, x2, y2;
int dire[300], newdire[4][300];
int h, t, pre[N*N * 5];
vector <pair<int, pair<int, int> > > v[N + 5][N + 5][4];
vector <pair<int, int> > ans;
abc dl[N*N * 5];
void wujie() {
puts("");
puts("
No Solution Possible");
}
bool bfs(int x, int y, int fx) {
h = 0, t = 1;
memset(bo, INF, sizeof bo);
memset(pre, 0, sizeof pre);
dl[1].dir = fx; dl[1].x = x; dl[1].y = y;
bo[x][y][fx] = 1;
if (x==x2 && y == y2) return true;
while (h < t) {
h++;
int tx = dl[h].x, ty = dl[h].y, before = dl[h].dir;
for (auto temp : v[tx][ty][before]) {
int xx = tx + temp.second.first, yy = ty + temp.second.second;
if (xx < 1 || xx > 9 || yy <1 || yy > 9) continue;
if (bo[xx][yy][temp.first]>bo[tx][ty][before] + 1) {
bo[xx][yy][temp.first] = bo[tx][ty][before] + 1;
t++;
dl[t].x = xx, dl[t].y = yy, dl[t].dir = temp.first;
pre[t] = h;
if (xx == x2 && yy == y2) return true;
}
}
}
return false;
}
void dfs(int now) {
if (now == 1) {
ans.push_back(make_pair(xx1, yy1));
ans.push_back(make_pair(dl[now].x, dl[now].y));
return;
}
dfs(pre[now]);
ans.push_back(make_pair(dl[now].x, dl[now].y));
}
int main() {
/*
freopen("rush.txt","r",stdin);
freopen("rush_out.txt","w",stdout);
*/
dire['N'] = 0, dire['S'] = 1, dire['W'] = 2, dire['E'] = 3;
newdire[0]['L'] = 2, newdire[0]['F'] = 0, newdire[0]['R'] = 3;
newdire[1]['L'] = 3, newdire[1]['R'] = 2, newdire[1]['F'] = 1;
newdire[2]['L'] = 1, newdire[2]['R'] = 0, newdire[2]['F'] = 2;
newdire[3]['L'] = 0, newdire[3]['R'] = 1, newdire[3]['F'] = 3;
string T;
while (cin >> T && T != "END") {
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++)
for (int k = 0; k < 4; k++)
v[i][j][k].clear();
scanf("%d%d", &xx1, &yy1);
char s[5];
scanf("%s", s);
scanf("%d%d", &x2, &y2);
int x, y;
while (scanf("%d", &x) && x) {
scanf("%d", &y);
char temp[5];
while (~scanf("%s", temp) && temp[0] != '*') {
int from = dire[temp[0]];
int len = strlen(temp);
for (int i = 1; i < len; i++) {
int temp1 = newdire[from][temp[i]];
v[x][y][from].push_back(make_pair(temp1, make_pair(dx[temp1], dy[temp1])));
}
}
}
int dir1 = dire[s[0]];
int tx = xx1 + dx[dir1], ty = yy1 + dy[dir1];
cout << T;
if (tx < 1 || tx > 9 || ty < 1 || ty > 9 || !bfs(tx, ty, dir1)) {
wujie();
}
else {
ans.clear();
dfs(t);
bool first;
for (int i = 0; i < (int)ans.size(); i++) {
if (i % 10 == 0) {
puts(""); printf("
");
first = true;
}
if (!first) putchar(' ');
first = false;
printf("(%d,%d)", ans[i].first, ans[i].second);
}
puts("");
}
}
return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
//[where in,point]minimum dis
//0 up 1 down 2 left 3 right
const int dx[4] = { -1,1,0,0 };
const int dy[4] = { 0,0,-1,1 };
const int N = 9;
const int INF = 0x3f3f3f3f;
struct abc {
int dir, x, y;
};
int bo[N + 5][N + 5][4], xx1, yy1, x2, y2;
int dire[300], newdire[4][300];
int h, t, pre[N*N * 5];
vector <pair<int, pair<int, int> > > v[N + 5][N + 5][4];
vector <pair<int, int> > ans;
abc dl[N*N * 5];
void wujie() {
puts("");
puts("
No Solution Possible");
}
bool bfs(int x, int y, int fx) {
h = 0, t = 1;
memset(bo, INF, sizeof bo);
memset(pre, 0, sizeof pre);
dl[1].dir = fx; dl[1].x = x; dl[1].y = y;
bo[x][y][fx] = 1;
if (x==x2 && y == y2) return true;
while (h < t) {
h++;
int tx = dl[h].x, ty = dl[h].y, before = dl[h].dir;
for (auto temp : v[tx][ty][before]) {
int xx = tx + temp.second.first, yy = ty + temp.second.second;
if (xx < 1 || xx > 9 || yy <1 || yy > 9) continue;
if (bo[xx][yy][temp.first]>bo[tx][ty][before] + 1) {
bo[xx][yy][temp.first] = bo[tx][ty][before] + 1;
t++;
dl[t].x = xx, dl[t].y = yy, dl[t].dir = temp.first;
pre[t] = h;
if (xx == x2 && yy == y2) return true;
}
}
}
return false;
}
void dfs(int now) {
if (now == 1) {
ans.push_back(make_pair(xx1, yy1));
ans.push_back(make_pair(dl[now].x, dl[now].y));
return;
}
dfs(pre[now]);
ans.push_back(make_pair(dl[now].x, dl[now].y));
}
int main() {
/*
freopen("rush.txt","r",stdin);
freopen("rush_out.txt","w",stdout);
*/
dire['N'] = 0, dire['S'] = 1, dire['W'] = 2, dire['E'] = 3;
newdire[0]['L'] = 2, newdire[0]['F'] = 0, newdire[0]['R'] = 3;
newdire[1]['L'] = 3, newdire[1]['R'] = 2, newdire[1]['F'] = 1;
newdire[2]['L'] = 1, newdire[2]['R'] = 0, newdire[2]['F'] = 2;
newdire[3]['L'] = 0, newdire[3]['R'] = 1, newdire[3]['F'] = 3;
string T;
while (cin >> T && T != "END") {
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++)
for (int k = 0; k < 4; k++)
v[i][j][k].clear();
scanf("%d%d", &xx1, &yy1);
char s[5];
scanf("%s", s);
scanf("%d%d", &x2, &y2);
int x, y;
while (scanf("%d", &x) && x) {
scanf("%d", &y);
char temp[5];
while (~scanf("%s", temp) && temp[0] != '*') {
int from = dire[temp[0]];
int len = strlen(temp);
for (int i = 1; i < len; i++) {
int temp1 = newdire[from][temp[i]];
v[x][y][from].push_back(make_pair(temp1, make_pair(dx[temp1], dy[temp1])));
}
}
}
int dir1 = dire[s[0]];
int tx = xx1 + dx[dir1], ty = yy1 + dy[dir1];
cout << T;
if (tx < 1 || tx > 9 || ty < 1 || ty > 9 || !bfs(tx, ty, dir1)) {
wujie();
}
else {
ans.clear();
dfs(t);
bool first;
for (int i = 0; i < (int)ans.size(); i++) {
if (i % 10 == 0) {
puts(""); printf("
");
first = true;
}
if (!first) putchar(' ');
first = false;
printf("(%d,%d)", ans[i].first, ans[i].second);
}
puts("");
}
}
return 0;
}