题解 | #合格的机器#

D

#include <bits/stdc++.h>
#define int long long

using namespace std;

#define gcd __gcd
#define int128 __int128
#define FP(prec) fixed << setprecision(prec)

template <int x>
using arr = array<int, x>;

typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;

const int P = 13331;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int M = 2 * N;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void solve() {
	int n, m;
	string s;
	cin >> n >> m >> s;
	int t = s.size();
	vector<vector<char>> a(n + 1, vector<char>(m + 1));
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= m; j ++) {
			cin >> a[i][j];
		}
	}
	unordered_map<char, int> d;
	d['U'] = 0, d['D'] = 1, d['L'] = 2, d['R'] = 3;
	vector<vector<int>> q(t, vector<int>(4));
	//第k*t + i秒，上下左右花费最少时间为q[i][0/1/2/3]
	//如果q[i][0/1/2/3]==LLONG_MAX，那么需要手动次数+1来移动
	vector<int> e(4, LLONG_MAX);
	for(int i = t - 1; i >= 0; i --) {
		e[d[s[i]]] = i;
		for(int j = 0; j < 4; j ++) {
			if(e[j] == LLONG_MAX) q[i][j] = e[j];
			else q[i][j] = e[j] - i + 1;
		}
	}
	vector<int> ee(4, LLONG_MAX);
	for(int i = 0; i < t; i ++) {
		ee[d[s[i]]] = min(ee[d[s[i]]], i);
		for(int j = 0; j < 4; j ++) {
			if(ee[j] != LLONG_MAX) q[i][j] = min(q[i][j], t - (i - ee[j]) + 1);
		}
	}
	vector<vector<int>> ft(n + 1, vector<int>(m + 1, LLONG_MAX)); //最少手动次数下的最少时间
	auto fd = ft;//最小手动次数
	fd[1][1] = ft[1][1] = 0;
	priority_queue<arr<4>, vector<arr<4>>, greater<arr<4>>> pq;
	pq.push({0, 0, 1, 1});
	while(pq.size()) {
		auto [cnt, tt, x, y] = pq.top();
		if(x == n && y == m) break;
		pq.pop();
		for(int i = 0; i < 4; i ++) {
			int xx = x + dx[i], yy = y + dy[i];
			if(xx < 1 || yy < 1 || xx > n || yy > m || a[xx][yy] == '#') continue;
			if(q[tt % t][i] == LLONG_MAX) {
				if(fd[xx][yy] > cnt + 1 || fd[xx][yy] == cnt + 1 && ft[xx][yy] > tt + 1) {
					pq.push({cnt + 1, tt + 1, xx, yy});
					fd[xx][yy] = cnt + 1;
					ft[xx][yy] = tt + 1;
				}
			}
			else {
				if(fd[xx][yy] > cnt || fd[xx][yy] == cnt && ft[xx][yy] > tt + q[tt % t][i]) {
					pq.push({cnt, tt + q[tt % t][i], xx, yy});
					fd[xx][yy] = cnt;
					ft[xx][yy] = tt + q[tt % t][i];
				}
			}
		}
	}
	cout << fd[n][m] << ' ' << ft[n][m] << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --) solve();
    return 0;
}