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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#define init(x) memset (x,INF,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2005;
const int MOD = 1e9 + 7;
inline int read ();
struct node
{
int x,y,cos,dir;
bool operator < (const node &a) const {
return cos > a.cos;
}
};
priority_queue <node> q;
int n,m,a,b,c,d,ans = INF,dis[MAX][MAX][5];
char str[MAX][MAX];
int main ()
{
n = read ();m = read ();a = read (),b = read (),c = read (),d = read ();
for (int i = 1;i <= n;++i) scanf ("%s",str[i] + 1);
for (int i = 1;i <= n;++i)
{
for (int j = 1;j <= m;++j)
{
if (str[i][j] == 'S')
{
q.push ({i,j,0,1});
q.push ({i,j,0,2});
q.push ({i,j,0,3});
q.push ({i,j,0,4});
}
}
}
init (dis);
while (!q.empty ())
{
node now = q.top ();q.pop ();
if (now.x < 1 || now.x > n || now.y < 1 || now.y > m) continue;
if (str[now.x][now.y] == '#') continue;
if (str[now.x][now.y] == 'E')
{
ans = min (ans,now.cos);
break;
}
if (dis[now.x][now.y][now.dir] <= now.cos) continue;
dis[now.x][now.y][now.dir] = now.cos;
if (now.dir == 1)
{
if (str[now.x][now.y] == 'S') q.push ({now.x - 1,now.y,now.cos,1});
if (str[now.x][now.y] == '|') q.push ({now.x - 1,now.y,now.cos + a,1});
if (str[now.x][now.y] == '-') q.push ({now.x,now.y - 1,now.cos + a,3}),q.push ({now.x,now.y + 1,now.cos + a,4});
if (str[now.x][now.y] == '/') q.push ({now.x,now.y + 1,now.cos + b,4});
if (str[now.x][now.y] == '\\') q.push ({now.x,now.y - 1,now.cos + b,3});
if (str[now.x][now.y] == '.') q.push ({now.x - 1,now.y,now.cos + c,1}),q.push ({now.x,now.y - 1,now.cos + c,3}),q.push ({now.x,now.y + 1,now.cos + c,4});
if (str[now.x][now.y] == '<') q.push ({now.x,now.y - 1,now.cos + d,3});
if (str[now.x][now.y] == '>') q.push ({now.x,now.y + 1,now.cos + d,4});
if (str[now.x][now.y] == '^') q.push ({now.x - 2,now.y,now.cos,1});
if (str[now.x][now.y] == 'v') ;
}
if (now.dir == 2)
{
if (str[now.x][now.y] == 'S') q.push ({now.x + 1,now.y,now.cos,2});
if (str[now.x][now.y] == '|') q.push ({now.x + 1,now.y,now.cos + a,2});
if (str[now.x][now.y] == '-') q.push ({now.x,now.y - 1,now.cos + a,3}),q.push ({now.x,now.y + 1,now.cos + a,4});
if (str[now.x][now.y] == '/') q.push ({now.x,now.y - 1,now.cos + b,3});
if (str[now.x][now.y] == '\\') q.push ({now.x,now.y + 1,now.cos + b,4});
if (str[now.x][now.y] == '.') q.push ({now.x + 1,now.y,now.cos + c,2}),q.push ({now.x,now.y - 1,now.cos + c,3}),q.push ({now.x,now.y + 1,now.cos + c,4});
if (str[now.x][now.y] == '<') q.push ({now.x,now.y - 1,now.cos + d,3});
if (str[now.x][now.y] == '>') q.push ({now.x,now.y + 1,now.cos + d,4});
if (str[now.x][now.y] == '^') ;
if (str[now.x][now.y] == 'v') q.push ({now.x + 2,now.y,now.cos,2});
}
if (now.dir == 3)
{
if (str[now.x][now.y] == 'S') q.push ({now.x,now.y - 1,now.cos,3});
if (str[now.x][now.y] == '|') q.push ({now.x - 1,now.y,now.cos + a,1}),q.push ({now.x + 1,now.y,now.cos + a,2});
if (str[now.x][now.y] == '-') q.push ({now.x,now.y - 1,now.cos + a,3});
if (str[now.x][now.y] == '/') q.push ({now.x + 1,now.y,now.cos + b,2});
if (str[now.x][now.y] == '\\') q.push ({now.x - 1,now.y,now.cos + b,1});
if (str[now.x][now.y] == '.') q.push ({now.x,now.y - 1,now.cos + c,3}),q.push ({now.x - 1,now.y,now.cos + c,1}),q.push ({now.x + 1,now.y,now.cos + c,2});
if (str[now.x][now.y] == '<') q.push ({now.x,now.y - 2,now.cos,3});
if (str[now.x][now.y] == '>') ;
if (str[now.x][now.y] == '^') q.push ({now.x - 1,now.y,now.cos + d,1});
if (str[now.x][now.y] == 'v') q.push ({now.x + 1,now.y,now.cos + d,2});
}
if (now.dir == 4)
{
if (str[now.x][now.y] == 'S') q.push ({now.x,now.y + 1,now.cos,4});
if (str[now.x][now.y] == '|') q.push ({now.x - 1,now.y,now.cos + a,1}),q.push ({now.x + 1,now.y,now.cos + a,2});
if (str[now.x][now.y] == '-') q.push ({now.x,now.y + 1,now.cos + a,4});
if (str[now.x][now.y] == '/') q.push ({now.x - 1,now.y,now.cos + b,1});
if (str[now.x][now.y] == '\\') q.push ({now.x + 1,now.y,now.cos + b,2});
if (str[now.x][now.y] == '.') q.push ({now.x,now.y + 1,now.cos + c,4}),q.push ({now.x - 1,now.y,now.cos + c,1}),q.push ({now.x + 1,now.y,now.cos + c,2});
if (str[now.x][now.y] == '<') ;
if (str[now.x][now.y] == '>') q.push ({now.x,now.y + 2,now.cos,4});
if (str[now.x][now.y] == '^') q.push ({now.x - 1,now.y,now.cos + d,1});
if (str[now.x][now.y] == 'v') q.push ({now.x + 1,now.y,now.cos + d,2});
}
}
if (ans == INF) printf ("-1\n");
else printf ("%d\n",ans);
return 0;
}
inline int read ()
{
int s = 0;int f = 1;
char ch = getchar ();
while ((ch < '0' || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
|
