注 1：這場(chǎng)比賽 GYM 上的題號(hào)與題目上的不一樣，這里以 GYM 內(nèi)提交的題號(hào)為準(zhǔn)
注 2：題目順序?yàn)槲覀€(gè)人提交的通過(guò)順序，因?yàn)檫@場(chǎng) GYM 是我一個(gè)人打的所以開(kāi)題的順序會(huì)比較奇怪
題目分析
A. Alphabet
因?yàn)榭梢栽谌我馕恢妹赓M(fèi)刪除字符它改，并且添加字符也可以在任意位置進(jìn)行积仗。所以答案就是 26 - LIS(s) 攀细。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 55;
char s[maxn];
int dp[maxn];
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1), ans = 0;
FOR(i, 1, n) dp[i] = 1;
FOR(i, 2, n) FOR(j, 1, i - 1) if (s[i] > s[j]) chkmax(dp[i], dp[j] + 1);
FOR(i, 1, n) chkmax(ans, dp[i]);
printf("%d", 26 - ans);
}
F. Equality
簽到題。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
int a, b, c;
int main() {
scanf("%d + %d = %d", &a, &b, &c);
puts(a + b == c ? "YES" : "NO");
}
G. Gravity
模擬爱态。不過(guò)我覺(jué)得可能有 O(n × m) 的做法谭贪？
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 55;
char mat[maxn][maxn];
int n, m;
int main() {
scanf("%d%d", &n, &m);
FOR(i, 1, n) scanf("%s", mat[i] + 1);
FOR(i, 1, m) {
int en = n;
ROF(j, n, 1) {
if (mat[j][i] == '#') en = j - 1;
else if (mat[j][i] == 'o')
ROF(k, en, j + 1) if (mat[k][i] == '.') {
swap(mat[k][i], mat[j][i]);
break;
}
}
}
FOR(i, 1, n) printf("%s\n", mat[i] + 1);
}
K. Six Sides
暴力。因?yàn)槊總€(gè)骰子只有 6 個(gè)面锦担，所以我們可以遍歷所有可能的 6 × 6 種情況俭识，用第一個(gè)人獲勝的情況數(shù)除以非平局情況數(shù)就可以了。
但是這個(gè)題數(shù)據(jù)可能比較弱洞渔，因?yàn)榘凑疹}目的定義套媚，我們要計(jì)算的是第一個(gè)人的獲勝概率。如果兩個(gè)骰子上 12 個(gè)面的所有數(shù)字都一樣磁椒，這個(gè)游戲不會(huì)結(jié)束堤瘤，所以第一個(gè)人也不會(huì)獲勝？然而沒(méi)有特判的提交也通過(guò)了浆熔。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
int d[2][6], cnt[2];
int main() {
REP(i, 2) REP(j, 6) scanf("%d", &d[i][j]);
REP(i, 6) REP(j, 6) {
if (d[0][i] == d[1][j]) continue;
if (d[0][i] > d[1][j]) cnt[0]++;
cnt[1]++;
}
if (!cnt[1]) cnt[1]++;
printf("%.5lf", double(cnt[0]) / cnt[1]);
}
M. Zigzag
動(dòng)態(tài)規(guī)劃本辐。用 dp[i][0/1] 表示以 a[i] 結(jié)尾的 Zigzag 子序列其中最后一次更新是下降/上升的最大長(zhǎng)度。于是原來(lái)的問(wèn)題就被轉(zhuǎn)化為兩個(gè)獨(dú)立的類(lèi) LIS 問(wèn)題医增。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 55;
int a[maxn], dp[maxn][2], n, ans;
int main() {
scanf("%d", &n);
FOR(i, 1, n) scanf("%d", a + i);
FOR(i, 1, n) {
dp[1][0] = dp[1][1] = 1;
FOR(j, 1, i - 1){
if (a[j] > a[i]) chkmax(dp[i][0], dp[j][1] + 1);
if (a[j] < a[i]) chkmax(dp[i][1], dp[j][0] + 1);
}
}
FOR(i, 1, n) REP(j, 2) chkmax(ans, dp[i][j]);
printf("%d", ans);
}
H. Islands
這個(gè)題的難點(diǎn)在于如何把戰(zhàn)爭(zhēng)迷霧染成陸地或者是水域慎皱。如果把邊界全部看成水域的話，對(duì)于任意一片戰(zhàn)爭(zhēng)迷霧叶骨，其可能的邊界情況是：
- 全部邊界都是水域
- 邊界有水域有陸地
- 全部邊界都是陸地
顯然對(duì)于第一種情況茫多，我們希望這片戰(zhàn)爭(zhēng)迷霧完全是水域，不然會(huì)平添一個(gè)島嶼邓萨。對(duì)于后兩種情況地梨，如果把這片戰(zhàn)爭(zhēng)迷霧全部染色成陸地的話菊卷，無(wú)論如何不會(huì)增加新的島嶼。相反地宝剖，如果該戰(zhàn)爭(zhēng)迷霧與兩片（或多片）本不連通的陸地鄰接洁闰，那么這種染法可能會(huì)減少島嶼的個(gè)數(shù)。
染色以后搜索就可以了万细。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 55;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
char mat[maxn][maxn];
int vis[maxn][maxn], clk, n, m;
bool flag[maxn * maxn];
void dfs1(int x, int y) {
if (vis[x][y]) return;
vis[x][y] = clk;
REP(i, 4) {
int nx = x + dx[i], ny = y + dy[i];
if (mat[nx][ny] == 'L') flag[clk] = true;
if (mat[nx][ny] == 'C') dfs1(nx, ny);
}
}
void dfs2(int x, int y) {
if (vis[x][y]) return;
vis[x][y] = 1;
REP(i, 4) {
int nx = x + dx[i], ny = y + dy[i];
if (mat[nx][ny] == 'L') dfs2(nx, ny);
}
}
int main() {
scanf("%d%d", &n, &m);
reset(mat, 'W');
FOR(i, 1, n) scanf("%s", mat[i] + 1);
FOR(i, 1, n) FOR(j, 1, m) if (mat[i][j] == 'C' && !vis[i][j]) {
clk++;
dfs1(i, j);
}
FOR(i, 1, n) FOR(j, 1, m) if (flag[vis[i][j]]) mat[i][j] = 'L';
reset(vis, 0);
int ans = 0;
FOR(i, 1, n) FOR(j, 1, m) if (mat[i][j] == 'L' && !vis[i][j]) {
ans++;
dfs2(i, j);
}
printf("%d", ans);
}
B. Barbells
暴力扑眉。因?yàn)?m 很小，不超過(guò) 14 赖钞，所以子集生成或者 dfs 都可以處理出可能的杠鈴片重量腰素。然后再枚舉杠鈴桿即可。復(fù)雜度 O(m × 3m + mn × 2m) 雪营。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
int b[15], p[15], n, m;
set<ll> lis, ans;
void dfs(int i, ll l, ll r) {
if (i > m) return;
if (l == r) lis.insert(r + l);
dfs(i + 1, l + p[i + 1], r);
dfs(i + 1, l, r + p[i + 1]);
dfs(i + 1, l, r);
}
int main() {
scanf("%d%d", &n, &m);
FOR(i, 1, n) scanf("%d", b + i);
FOR(i, 1, m) scanf("%d", p + i);
dfs(0, 0, 0);
FOR(i, 1, n) for (auto it : lis) ans.insert(it + b[i]);
for (auto it : ans) printf("%lld\n", it);
}
E. Contest Score
用 std::multiset 模擬即可弓千。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 312;
int n, k, t[maxn];
int main() {
scanf("%d%d", &n, &k);
FOR(i, 1, n) scanf("%d", t + i);
multiset<int> tt;
FOR(i, 1, k) tt.insert(t[i]);
ll ans = 0, pre = 0;
while (!tt.empty()) {
pre += *tt.begin();
ans += pre;
tt.erase(tt.find(*tt.begin()));
if (k < n) tt.insert(t[++k]);
}
printf("%lld", ans);
}
D. Cameras
從前往后檢查每個(gè)長(zhǎng)度為 r 的窗口，滑動(dòng)地維護(hù)窗口內(nèi)的監(jiān)控?cái)?shù)目献起。如果發(fā)現(xiàn)當(dāng)前窗口內(nèi)的監(jiān)控?cái)?shù)目少于兩個(gè)洋访，那么貪心地從后往前把窗口內(nèi)的監(jiān)控?cái)?shù)目補(bǔ)足兩個(gè)即可。復(fù)雜度 O(n) 谴餐。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 112345;
int k, r, n;
bool vis[maxn];
int main() {
scanf("%d%d%d", &n, &k, &r);
REP(i, k) {
int p;
scanf("%d", &p);
vis[p] = true;
}
int cnt = 0, ans = 0;
FOR(i, 1, r - 1) cnt += vis[i];
FOR(i, r, n) {
cnt -= vis[i - r];
cnt += vis[i];
ROF(j, i, 1) {
if (cnt >= 2) break;
if (vis[j]) continue;
vis[j] = true;
cnt++, ans++;
}
}
printf("%d", ans);
}
L. Three Square
沒(méi)有什么技巧性的暴力姻政。比較惡心。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
pii lis[5];
int main() {
int s = 0;
REP(i, 3) {
scanf("%d%d", &lis[i]._1, &lis[i]._2);
if (lis[i]._1 < lis[i]._2) swap(lis[i]._1, lis[i]._2);
s += lis[i]._1 * lis[i]._2;
}
int a = sqrt(s) + 0.5;
if (a * a != s) {
puts("NO");
return 0;
}
sort(lis, lis + 3, greater<pii>());
bool ok = false;
if (lis[0]._1 == a) {
int b = a - lis[0]._2;
if (lis[1]._1 == lis[2]._1 && lis[1]._1 == a && lis[1]._2 + lis[2]._2 == b)
ok = true;
else if (lis[1]._1 == lis[2]._1 && lis[1]._1 == b && lis[1]._2 + lis[2]._2 == a)
ok = true;
else if (lis[1]._2 == lis[2]._2 && lis[1]._2 == b && lis[1]._1 + lis[2]._1 == a)
ok = true;
else if (lis[1]._2 == lis[2]._1 && lis[1]._2 == b && lis[1]._1 + lis[2]._2 == a)
ok = true;
}
puts(ok ? "YES" : "NO");
}
I. Mismatched Socks
我們先找出最多的那種襪子岂嗓，如果最多的襪子數(shù)量大于等于別的襪子的數(shù)量和汁展，那么盡可能配對(duì)以后輸出答案就可以了。如果小于厌殉，那么我們把最多的襪子放在左邊食绿，然后把其他襪子放在右邊，之后盡可能地把右邊的某種襪子全部移到左邊但同時(shí)保證左邊襪子數(shù)量不超過(guò)右邊年枕。這個(gè)過(guò)程結(jié)束后左邊的任意一只襪子都和右邊所有襪子的顏色不一樣炫欺。之后我任意挑選右邊的一種襪子，然后把它們盡可能移動(dòng)到左邊但保證左邊襪子數(shù)量不超過(guò)右邊熏兄。我們先用右邊該顏色剩下的襪子與左邊最多的襪子配對(duì)，一定可以把右邊的這部分襪子用完树姨。之后任意左右配對(duì)即可摩桶。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 1123;
ll lis[maxn];
int n;
int main() {
scanf("%d", &n);
FOR(i, 1, n) scanf("%lld", &lis[i]);
sort(lis + 1, lis + n + 1);
ll mm = 0;
FOR(i, 1, n - 1) mm += lis[i];
if (mm <= lis[n]) printf("%lld", mm);
else printf("%lld", mm + lis[n] >> 1);
}
J. Postman
首先很容易注意到我們無(wú)論何時(shí)均不應(yīng)該在同一次投遞過(guò)程中同時(shí)去原點(diǎn)左右兩側(cè)。因此帽揪，我們將原點(diǎn)兩側(cè)的信箱分開(kāi)處理硝清。對(duì)于某一側(cè)，我們可以從遠(yuǎn)到近投遞转晰，如果某一次投遞數(shù)量不足 K芦拿，那么我們可以順便從遠(yuǎn)到近投遞剩下的信箱士飒，直到?jīng)]有多余的背包空間或沒(méi)有需要投遞的信件方返程。復(fù)雜度 O(nlogn) 蔗崎。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
int n, k;
ll ans;
priority_queue<pii> lis[2];
void solve(priority_queue<pii> &q) {
while (!q.empty()) {
auto now = q.top(); q.pop();
int x = now._1, m = now._2;
ans += m / k * ll(x) * 2;
m -= m / k * k;
if (!m) continue;
ans += 2 * x;
int rem = k - m;
while (rem && !q.empty()) {
auto cur = q.top(); q.pop();
if (rem >= cur._2) {
rem -= cur._2;
continue;
}
cur._2 -= rem;
rem = 0;
q.push(cur);
}
}
}
int main() {
scanf("%d%d", &n, &k);
FOR(i, 1, n) {
int x, m;
scanf("%d%d", &x, &m);
if (!x) continue;
if (x < 0) lis[0].push(mp(-x, m));
else lis[1].push(mp(x, m));
}
solve(lis[0]);
solve(lis[1]);
printf("%lld", ans);
}
C. Buggy Robot
動(dòng)態(tài)規(guī)劃酵幕。用 dp[x][y][pos] 表示當(dāng)前在網(wǎng)絡(luò)內(nèi)點(diǎn) (x, y) 且將要執(zhí)行第 pos 個(gè)指令時(shí)最少修改多少次。如果 pos 位置還有指令缓苛，那么可以用當(dāng)前狀態(tài)免費(fèi)地遵循指令更新或者花費(fèi)一次修改來(lái)刪除該指令芳撒。在任意時(shí)候都可以花費(fèi)一次修改來(lái)讓機(jī)器人移動(dòng)要鄰接的合法位置∥辞牛可以用類(lèi)似于 Dijkstra 算法的方法來(lái)更新?tīng)顟B(tài)笔刹。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define ROF(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define REP(i, n) FOR(i, 0, (n)-1)
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define reset(x, y) memset(x, y, sizeof(x))
#define uni(x) (x).erase(unique(all(x)), (x).end());
#define BUG(x) cerr << #x << " = " << (x) << endl
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define _1 first
#define _2 second
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
const int maxn = 55;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int dp[maxn][maxn][maxn], n, m, len;
char mat[maxn][maxn], cmd[maxn];
typedef pair<pii, pii> Node;
int main() {
scanf("%d%d", &n, &m);
FOR(i, 1, n) scanf("%s", mat[i] + 1);
scanf("%s", cmd + 1);
len = strlen(cmd + 1);
reset(dp, 0x3f);
int sx, sy, tx, ty;
FOR(i, 1, n) FOR(j, 1, m) {
if (mat[i][j] == 'R') sx = i, sy = j;
if (mat[i][j] == 'E') tx = i, ty = j;
}
dp[sx][sy][1] = 0;
set<Node> s;
s.insert(mp(mp(0, 1), mp(sx, sy)));
while (!s.empty()) {
auto now = *s.begin(); s.erase(now);
int used = now._1._1, pos = now._1._2, x = now._2._1, y = now._2._2;
if (used > dp[x][y][pos]) continue;
if (x == tx && y == ty) {
printf("%d", used);
return 0;
}
if (pos != len + 1) {
int nx = x, ny = y, np = pos + 1;
if (cmd[pos] == 'U' && nx != 1 && mat[nx - 1][ny] != '#') nx--;
if (cmd[pos] == 'D' && nx != n && mat[nx + 1][ny] != '#') nx++;
if (cmd[pos] == 'L' && ny != 1 && mat[nx][ny - 1] != '#') ny--;
if (cmd[pos] == 'R' && ny != m && mat[nx][ny + 1] != '#') ny++;
if (dp[nx][ny][np] > used) {
dp[nx][ny][np] = used;
s.insert(mp(mp(used, np), mp(nx, ny)));
}
if (dp[x][y][np] > used + 1) {
dp[x][y][np] = used + 1;
s.insert(mp(mp(used + 1, np), mp(x, y)));
}
}
REP(i, 4) {
int nx = x + dx[i], ny = y + dy[i];
if (!nx) nx++;
if (nx == n + 1) nx--;
if (!ny) ny++;
if (ny == m + 1) ny--;
if (mat[nx][ny] == '#') nx -= dx[i], ny -= dy[i];
if (dp[nx][ny][pos] > used + 1) {
dp[nx][ny][pos] = used + 1;
s.insert(mp(mp(used + 1, pos), mp(nx, ny)));
}
}
}
}
