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
|
BEGIN {
FS = "";
y = 1;
}
function elev(a) {
return index("abcdefghijklmnopqrstuvwxyz", a);
}
{
for (x = 1; x <= NF; ++x) {
if ($x == "S") {
S = x "," y;
m[x,y] = elev("a");
} else if ($x == "E") {
E = x "," y;
m[x,y] = elev("z");
} else {
m[x,y] = elev($x);
}
}
y++;
w = NF;
h = NR;
}
END {
l = 1;
Q[l] = S;
N[l] = 0;
for (i = 1; Q[i]; ++i) {
if (Q[i] == E) break;
split(Q[i], a, ",");
x = a[1];
y = a[2];
n = N[i];
if (x > 1 && !V[x-1,y] && m[x-1,y] <= m[x,y]+1) {
V[x-1,y] = 1;
Q[++l] = x-1 "," y;
N[l] = n+1;
}
if (x < w && !V[x+1,y] && m[x+1,y] <= m[x,y]+1) {
V[x+1,y] = 1;
Q[++l] = x+1 "," y;
N[l] = n+1;
}
if (y > 1 && !V[x,y-1] && m[x,y-1] <= m[x,y]+1) {
V[x,y-1] = 1;
Q[++l] = x "," y-1;
N[l] = n+1;
}
if (y < h && !V[x,y+1] && m[x,y+1] <= m[x,y]+1) {
V[x,y+1] = 1;
Q[++l] = x "," y+1;
N[l] = n+1;
}
delete Q[i];
delete N[i];
}
print N[i];
delete Q;
delete N;
delete V;
l = 1;
Q[l] = E;
N[l] = 0;
for (i = 1; Q[i]; ++i) {
split(Q[i], a, ",");
x = a[1];
y = a[2];
n = N[i];
if (m[x,y] == 1) break;
if (x > 1 && !V[x-1,y] && m[x-1,y] >= m[x,y]-1) {
V[x-1,y] = 1;
Q[++l] = x-1 "," y;
N[l] = n+1;
}
if (x < w && !V[x+1,y] && m[x+1,y] >= m[x,y]-1) {
V[x+1,y] = 1;
Q[++l] = x+1 "," y;
N[l] = n+1;
}
if (y > 1 && !V[x,y-1] && m[x,y-1] >= m[x,y]-1) {
V[x,y-1] = 1;
Q[++l] = x "," y-1;
N[l] = n+1;
}
if (y < h && !V[x,y+1] && m[x,y+1] >= m[x,y]-1) {
V[x,y+1] = 1;
Q[++l] = x "," y+1;
N[l] = n+1;
}
delete Q[i];
delete N[i];
}
print N[i];
}
|