CF1753D Beach Sol

看到这种要先满足某个条件才能满足另一个条件的题目，想到图论。

假设当前有一个 \(c_{i,j}=\) L，\(c_{i,j+1}=\) R，那么如果要把其右移一格就需要满足 \(c_{i,j+2}\) 当前空出来。也就是说，我们需要先满足 \((i,j+2)\) 的条件才能满足 \((i,j)\) 的条件。可以抽象为由 \((i,j+2)\) 向 \((i,j)\) 连一条边，代价为 \(q\)。

同理，对于旋转操作，以 \((i,j)\) 为中心，可以将 \((i,j+1)\) 旋转到 \((i-1,j)\)，那么要使其满足 \((i-1,j+1)\) 和 \((i+1,j+1)\) 必须有一个地方能空出来，所以从 \((i-1,j+1)\) 和 \((i+1,j+1)\) 向 \((i,j)\) 连边，代价为 \(p\)。

同理可以这样处理 R，U，D。

对于原本为 . 的地方可以作为起点。

跑 Dijkstra 即可。复杂度 \(O((nm)\log(nm))\)。

#include <bits/stdc++.h>
#define int long long
#define pii pair <int, int>
using namespace std;

const int N = 3e5 + 10;
int T, n, m, p, q, dis[N]; bool vis[N];
vector <char> Map[N]; vector <pii> g[N];
priority_queue <pii, vector <pii>, greater <pii> > que;
inline int chg(int x, int y) { return (x - 1) * m + y; }

inline void solve() {
  cin >> n >> m >> p >> q;
  memset(dis, 0x3f, sizeof(dis));
  for (int i = 1; i <= n; ++i) Map[i].resize(m + 1);
  for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> Map[i][j];
  for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
    int id = chg(i, j); if (Map[i][j] == '.') que.push({dis[id] = 0, id});
    auto addEdge = [&] (int x, int y, int val) {
      if (x < 1 || x > n || y < 1 || y > m) return ;
      g[chg(x, y)].push_back({id, val});
    };
    if (Map[i][j] == 'L') {
      addEdge(i - 1, j + 1, p), addEdge(i + 1, j + 1, p);
      addEdge(i, j + 2, q);
    } else if (Map[i][j] == 'R') {
      addEdge(i - 1, j - 1, p), addEdge(i + 1, j - 1, p);
      addEdge(i, j - 2, q);
    } else if (Map[i][j] == 'U') {
      addEdge(i + 1, j - 1, p), addEdge(i + 1, j + 1, p);
      addEdge(i + 2, j, q);
    } else if (Map[i][j] == 'D') {
      addEdge(i - 1, j - 1, p), addEdge(i - 1, j + 1, p);
      addEdge(i - 2, j, q);
    }
  }
  while (!que.empty()) {
    int cur = que.top().second; que.pop();
    if (vis[cur]) continue; vis[cur] = true;
    for (auto [to, val]: g[cur]) {
      if (dis[to] > dis[cur] + val) {
        dis[to] = dis[cur] + val;
        que.push({dis[to], to});
      }
    }
  }
  int res = 1e18;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      if (i ^ n) res = min(res, dis[chg(i, j)] + dis[chg(i + 1, j)]);
      if (j ^ m) res = min(res, dis[chg(i, j)] + dis[chg(i, j + 1)]);
    }
  cout << (res == 1e18? -1 : res) << endl;
  return ;
}

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
  T = 1; while (T--) solve();
  return 0;
}