测评记录qwq：https://codeforces.com/contest/1753/submission/195279906

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
struct edge {
	LL w, next, to;
} e[N];
struct node {
	LL pos, w;
	node(int _, int __) :
		pos(_), w(__) {}
	bool operator < (const node& x) const {
		return x.w < w;
	}
};
LL n, m, x, y, tot, cnt, ans = LLONG_MAX, dis[N], head[N];
priority_queue<node> q;
bool vis[N];
vector<char> ch[N];
vector<int> pos[N];
void add(int u, int v, int w) {
	e[++ cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void dijkstra() {
	while (!q.empty()) {
		node u = q.top();
		q.pop();
		if (vis[u.pos]) continue;
		vis[u.pos] = true;
		for (int i = head[u.pos]; i; i = e[i].next) {
			int v = e[i].to;
			if (dis[v] > dis[u.pos] + e[i].w) {
				dis[v] = dis[u.pos] + e[i].w;
				if (!vis[v]) q.push(node(v, dis[v]));
			}
		}
	}
}
bool check(int x, int y) {
	return 1 <= x && x <= n && 1 <= y && y <= m && ch[x][y] != '#';
}
void Add(int u, int v, int w) {
//	cout << "Added " << u << ' ' << v << ' ' << w << '\n';
	add(u, v, w), add(v, u, w);
}
void Addqwq(int x1, int y1, int x2, int y2, int w) {
	if (check(x1, y1) && check(x2, y2))
		Add(pos[x1][y1], pos[x2][y2], w);
}
int main() {
	memset(dis, 0x3f, sizeof dis);
	cin >> n >> m >> y >> x;
	for (int i = 1; i <= n; i ++) {
		ch[i].reserve(m + 5), pos[i].reserve(m + 5);
		for (int j = 1; j <= m; j ++)
			cin >> ch[i][j], pos[i][j] = ++ tot;
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++) {
			switch (ch[i][j]) {
				case '#': break;
				case '.': q.push(node(pos[i][j], 0)), dis[pos[i][j]] = 0; break;
				case 'L':
					if (check(i, j + 2)) Add(pos[i][j], pos[i][j + 2], x);
					Addqwq(i, j + 1, i - 1, j, y), Addqwq(i, j + 1, i + 1, j, y);
					break;
				case 'R':
					if (check(i, j - 2)) Add(pos[i][j], pos[i][j - 2], x);
					Addqwq(i, j - 1, i - 1, j, y), Addqwq(i, j - 1, i + 1, j, y);
					break;
				case 'U':
					if (check(i + 2, j)) Add(pos[i][j], pos[i + 2][j], x);
					Addqwq(i + 1, j, i, j - 1, y), Addqwq(i + 1, j, i, j + 1, y);
					break;
				case 'D':
					if (check(i - 2, j)) Add(pos[i][j], pos[i - 2][j], x);
					Addqwq(i - 1, j, i, j - 1, y), Addqwq(i - 1, j, i, j + 1, y);
					break;
			}
		}
	dijkstra();
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			if (check(i, j + 1)) ans = min(ans, dis[pos[i][j]] + dis[pos[i][j + 1]]);
			if (check(i + 1, j)) ans = min(ans, dis[pos[i][j]] + dis[pos[i + 1][j]]);
//			cout << dis[pos[i][j]] << ' ';
		}
//		cout << '\n';
	}
	if (ans > 1e15) puts("-1");
	else cout << ans << '\n';
	return 0;
}