α+β Problem

· · 题解

出题人题解。

部分分

子任务 0 考虑枚举每个位置是否放箱子再验证合法性。

子任务 1 保证了不同位置很少，也可以搜索。

子任务 2 留给可能过的网络流等算法。

子任务 3 分两种情况，对向则最多放两个，否则考虑尽可能在每个拐角放。

子任务 4 用于启发正解，做法和正解差不多。

正解

首先墙壁是诈骗，最优解肯定不用放墙。

假如我们在地图里放了多个箱子，那么这些箱子一定互不影响，即没有把一个箱子推进另一个箱子的情况。

由此我们可以假设地图上放满了箱子，用并查集维护移动过程。

最后在同一连通块的箱子只能放一个，注意箱子要动过的限制后随便选一个即可。

然后发现其实一个连通块只需要记录一个箱子的位置就可以了，于是在合并的时候优先记录被推动的箱子即可。

每组数据时间复杂度为 O(nm+k)。

#include<bits/stdc++.h>
#define CKE if(CHECK)
#define FRE if(FIL)
#define MX 2005
using namespace std;
const int CHECK=0,FIL=0;int read();
bitset<MX*MX> res,p;
int n,m,x,y,X,Y,f,a[MX*MX];string s;
int fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int Z(int i,int j){return i*m-m+j;}
int inMap(int i,int j){return i && j && i<=n && j<=m;}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    FRE freopen(".in","r",stdin);
    FRE freopen(".out","w",stdout);
    int T;cin>>T;while(T--){
        cin>>n>>m>>x>>y>>s>>s;X=x,Y=y,f=0;
        for(int i=1;i<=n*m;i++) a[i]=i,res[i]=p[i]=0;
        a[Z(x,y)]=0;
        for(auto i:s){
            if(i=='D') f=(f+1)%4;
            if(i=='A') f=(f+3)%4;
            if(i=='W'){
                int dx=x+fx[f][0],dy=y+fx[f][1];
                int wx=dx+fx[f][0],wy=dy+fx[f][1];
                if(a[Z(dx,dy)]){
                    if(inMap(wx,wy)) a[Z(wx,wy)]=a[Z(dx,dy)];
                    a[Z(dx,dy)]=0,p[Z(dx,dy)]=1;
                }
                x=dx,y=dy;
            }
            if(i=='S'){
                int dx=x-fx[f][0],dy=y-fx[f][1];
                a[Z(dx,dy)]=0;x=dx,y=dy;
            }
        }
        for(int i=1;i<=n*m;i++){
            if(!a[i]) continue;
            if(p[a[i]]) res[a[i]]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i==X && j==Y){cout<<"X"; continue;}
                if(res[Z(i,j)]){cout<<"S";}
                else cout<<".";
            }cout<<'\n';
        }
    }
    return 0;
}
int read(){
    int Ca=0;char Cr=' ';int Cf=1;
    while(Cr<'0' || Cr>'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
    while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
    return Ca*Cf;
}