CF1753D The Beach

Genius_Star · 2024-02-01 10:19:40 · 题解

思路：

注意到每一个障碍物的移动是相当于将一个空格移到另外一个地方，于是考虑以每一个空格能到的地方连边：

• 若 s_{i,j}=L，该障碍物有三种方式运动：

  • 平移：由 [s_{i,j},s_{i,j+1}] \to [s_{i,j+1},s_{i,j+2}]，即将 s_{i,j} 这个位置空出来，将 s_{i,j+2} 这个位置堵住，则我们可以 (i,j+2) \to (i,j) 连一条边权为 q 的单向边。

  • 顺时针旋转：由 [s_{i,j},s_{i,j+1}] \to [s_{i-1,j+1},s_{i,j+1}]，即将 s_{i,j} 这个位置空出来，将 s_{i-1,j+1} 这个位置堵住，则我们可以 (i-1,j+1) \to (i,j) 连一条边权为 p 的单向边。

  • 逆时针旋转：由 [s_{i,j},s_{i,j+1}] \to [s_{i,j+1},s_{i+1,j+1}]，即将 s_{i,j} 这个位置空出来，将 s_{i+1,j+1} 这个位置堵住，则我们可以 (i+1,j+1) \to (i,j) 连一条边权为 p 的单向边。

• 若 s_{i,j}=R，该障碍物有三种方式运动：

  • 平移：由 [s_{i,j-1},s_{i,j}] \to [s_{i,j-2},s_{i,j-1}]，即将 s_{i,j} 这个位置空出来，将 s_{i,j-2} 这个位置堵住，则我们可以 (i,j-2) \to (i,j) 连一条边权为 q 的单向边。

  • 顺时针旋转：由 [s_{i,j-1},s_{i,j}] \to [s_{i,j-1},s_{i+1,j-1}]，即将 s_{i,j} 这个位置空出来，将 s_{i+1,j-1} 这个位置堵住，则我们可以 (i+1,j-1) \to (i,j) 连一条边权为 p 的单向边。

  • 逆时针旋转：由 [s_{i,j-1},s_{i,j}] \to [s_{i-1,j-1},s_{i,j-1}]，即将 s_{i,j} 这个位置空出来，将 s_{i-1,j-1} 这个位置堵住，则我们可以 (i-1,j-1) \to (i,j) 连一条边权为 p 的单向边。

• 若 s_{i,j}=U，该障碍物有三种方式运动：

  • 平移：由 [s_{i,j},s_{i+1,j}] \to [s_{i+1,j},s_{i+2,j}]，即将 s_{i,j} 这个位置空出来，将 s_{i+2,j} 这个位置堵住，则我们可以 (i+2,j) \to (i,j) 连一条边权为 q 的单向边。

  • 顺时针旋转：由 [s_{i,j},s_{i+1,j}] \to [s_{i+1,j},s_{i+1,j+1}]，即将 s_{i,j} 这个位置空出来，将 s_{i+1,j+1} 这个位置堵住，则我们可以 (i+1,j+1) \to (i,j) 连一条边权为 p 的单向边。

  • 逆时针旋转：由 [s_{i,j},s_{i+1,j}] \to [s_{i+1,j-1},s_{i+1,j}]，即将 s_{i,j} 这个位置空出来，将 s_{i+1,j-1} 这个位置堵住，则我们可以 (i+1,j-1) \to (i,j) 连一条边权为 p 的单向边。

• 若 s_{i,j}=D，该障碍物有三种方式运动：

  • 平移：由 [s_{i-1,j},s_{i,j}] \to [s_{i-2,j},s_{i-1,j}]，即将 s_{i,j} 这个位置空出来，将 s_{i-2,j} 这个位置堵住，则我们可以 (i-2,j) \to (i,j) 连一条边权为 q 的单向边。

  • 顺时针旋转：由 [s_{i-1,j},s_{i,j}] \to [s_{i-1,j-1},s_{i-1,j}]，即将 s_{i,j} 这个位置空出来，将 s_{i-1,j-1} 这个位置堵住，则我们可以 (i-1,j-1) \to (i,j) 连一条边权为 p 的单向边。

  • 逆时针旋转：由 [s_{i-1,j},s_{i,j}] \to [s_{i-1,j},s_{i-1,j+1}]，即将 s_{i,j} 这个位置空出来，将 s_{i-1,j+1} 这个位置堵住，则我们可以 (i-1,j+1) \to (i,j) 连一条边权为 p 的单向边。

图建出来后，需要以每一个空格点为源点，跑单源最短路 Dijkstra 堆优化即可。

每次判断相邻两点都有空格到达的最短路径：dis_{i,j}+dis_{i,j+1} 或 dis_{i,j}+dis_{i+1,j}。

时间复杂度为 O(nm \log{nm})。

实现时注意判边界。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=300300;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
struct Node{
    ll y,x;
    bool operator<(const Node&rhs)const{
        return rhs.y<y;
    }
};
ll n,m,p,q,ans=1e18;
string s[N];
ll dis[N];
bool f[N];
priority_queue<Node> Q;
vector<pair<ll,ll>> E[N];
ll get(ll x,ll y){
    return (x-1)*m+y;
}
void add(ll u,ll v,ll w){
    E[u].push_back({v,w});
}
bool check(ll x,ll y){
    if(x<1||x>n||y<1||y>m)
      return 0;
    if(s[x][y]=='#')
      return 0;
    return 1;
}
void dijkstra(){
    while(!Q.empty()){
        Node t=Q.top();
        Q.pop();
        ll x=t.x;
        if(f[x])
          continue;
        f[x]=1;
        for(auto i:E[x]){
            ll y=i.first;
            if(dis[y]>dis[x]+i.second){
                dis[y]=dis[x]+i.second;
                if(!f[y])
                  Q.push({dis[y],y});
            }
        }
    }
}
int main(){
    memset(dis,0x3f,sizeof(dis));
    n=read(),m=read(),p=read(),q=read();
    for(int i=1;i<=n;i++){
        getline(cin,s[i]);
        s[i]=" "+s[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ll id=get(i,j); 
            if(s[i][j]=='.'){
                dis[id]=0;
                Q.push({0,id});
            }
            if(s[i][j]=='L'){
                if(check(i-1,j+1))
                  add(get(i-1,j+1),id,p);
                if(check(i+1,j+1))
                  add(get(i+1,j+1),id,p);
                if(check(i,j+2))
                 add(get(i,j+2),id,q);
            }
            else if(s[i][j]=='R'){
                if(check(i-1,j-1))
                  add(get(i-1,j-1),id,p);
                if(check(i+1,j-1))
                  add(get(i+1,j-1),id,p);
                if(check(i,j-2))
                  add(get(i,j-2),id,q);
            }
            else if(s[i][j]=='U'){
                if(check(i+1,j-1))
                  add(get(i+1,j-1),id,p);
                if(check(i+1,j+1))
                  add(get(i+1,j+1),id,p);
                if(check(i+2,j))
                  add(get(i+2,j),id,q);
            }
            else if(s[i][j]=='D'){
                if(check(i-1,j-1))
                  add(get(i-1,j-1),id,p);
                if(check(i-1,j+1))
                  add(get(i-1,j+1),id,p);
                if(check(i-2,j))
                  add(get(i-2,j),id,q);
            }
        }
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i!=n) 
              ans=min(ans,dis[get(i,j)]+dis[get(i+1,j)]);
            if(j!=m)
              ans=min(ans,dis[get(i,j)]+dis[get(i,j+1)]);
        }
    }
    write(ans==1e18?-1:ans);
    return 0;
}