USACO the Tamworth Two

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
/*
ID: wcr19961
PROG: ttwo
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
typedef long long LL;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int maxn = 12;
char g[maxn][maxn];
int len[maxn][maxn][4][maxn][maxn][4];
bool vis[maxn][maxn][4][maxn][maxn][4];
struct node {
int ax, ay, ad;
int bx, by, bd;
void Go(int a, int b, int& a0, int& b0, int& c) {
if (a >= 0 && a < 10 && b >= 0 && b < 10 && g[a][b] != '*') {
a0 = a, b0 = b;
} else {
c = (c + 1) % 4;
}
}
void Go() {
Go(ax + dx[ad], ay + dy[ad], ax, ay, ad);
Go(bx + dx[bd], by + dy[bd], bx, by, bd);
}
bool& Vis() {
return vis[ax][ay][ad][bx][by][bd];
}
int& Len() {
return len[ax][ay][ad][bx][by][bd];
}
bool Ok() {
return ax == bx && ay == by;
}
};
int main() {
freopen("ttwo.in", "r", stdin);
freopen("ttwo.out", "w", stdout);
node s;
for (int i = 0; i < 10; ++i) {
scanf("%s", g[i]);
for (int j = 0; j < 10; ++j) {
if (g[i][j] == 'C') {
s.ax = i, s.ay = j, s.ad = 0;
}
if (g[i][j] == 'F') {
s.bx = i, s.by = j, s.bd = 0;
}
}
}
s.Vis() = true;
queue<node> q;
q.push(s);
bool flag = false;
while (!q.empty()) {
node k = q.front();
q.pop();
int Len = k.Len();
if (k.Ok()) {
printf("%d\n", k.Len());
flag = true;
break;
}
k.Go();
if (!k.Vis()) {
k.Vis() = true;
k.Len() = Len + 1;
q.push(k);
}
}
if (!flag) {
puts("0");
}
return 0;
}

支付宝扫码领红包