题解 CF1578A Anti-Tetris

· · 题解

正着做是不好做的，因为我们不知道哪一块是最先放的，很难求出顺序的关系。

考虑倒着做，每次拿掉一个可以拿掉的，因为拿掉一个可以拿掉的连通块时不会影响其它连通块是否会被拿掉，即如果存在可行方案，每次将一个可以作为最后一个位置的连通块拿掉一定可行。

接下来可以直接模拟，每一次枚举所有连通块，bfs 检查是否可行，时间复杂度理论上是 O(n^6) 的，来源于模拟 O(n^2) 次，枚举 O(n^2) 个连通块，bfs 是 O(n^2) 的复杂度，但由于枚举到可行的连通块可以直接退出，枚举到不可行的连通块时 bfs 不会访问 O(n^2) 个位置，连通块大小不可能全 \leq 2 所以连通块个数也带着一个小常数，bfs 其实也是带一个小常数的，总的来说跑得很快。（可能有更正确的复杂度证明，很多自己口胡的不严谨的证明都存在一些恰好违背这个性质的极其特殊的反例，所以没有写出来）。

在模拟部分的一些细节可以参考代码：

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
    re int t=0;re char v=getchar();
    while(v<'0')v=getchar();
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return t;
}
const int M=998244353;
inline int ksm(re int x,re int y){
    re int s=1;
    while(y){
        if(y&1)s=1ll*s*x%M;
        x=1ll*x*x%M,y>>=1;
    }
    return s;
}
inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
inline int Mod(re int x){return x>=M?x-M:x;}
int n,m,X,Y,tot,px[2502],py[2502],ans1[2502],num;
string ans[2502];
char vis[52][52],s[52][52],cc[52][52];
struct node{int x,y;string S;};
inline bool ck(){
    for(re int i=1;i<=n;++i)
        for(re int j=1;j<=m;++j)
            if(s[i][j]!='.')return 1;
    return 0;
}
inline void bfs(re int x,re int y){
    if(vis[x][y])return;
    if(s[x][y]!=s[X][Y])return;
    vis[x][y]=1,px[++tot]=x-X,py[tot]=y-Y;
    bfs(x-1,y),bfs(x+1,y),bfs(x,y-1),bfs(x,y+1);
}
inline bool ck(re int x,re int y){
    if(cc[x][y])return 0;
    for(re int i=1;i<=tot;++i)if(s[x+px[i]][y+py[i]]!='.')return 0;
    cc[x][y]=1;
    return 1;
}
inline int Try(re int x,re int y){
    X=x,Y=y,tot=0,bfs(x,y);
    re char c=s[x][y];
    for(re int i=1;i<=tot;++i)s[x+px[i]][y+py[i]]='.';
    queue<node>Q;
    memset(cc,0,sizeof(cc));
    Q.push((node){x,y,""});
    while(!Q.empty()){
        re node z=Q.front();Q.pop();
        if(z.x==1){
            ans1[++num]=z.y;
            ans[num]=z.S+'S';
            return 1;
        }
        if(ck(z.x-1,z.y))Q.push((node){z.x-1,z.y,"D"+z.S});
        if(ck(z.x,z.y-1))Q.push((node){z.x,z.y-1,"R"+z.S});
        if(ck(z.x,z.y+1))Q.push((node){z.x,z.y+1,"L"+z.S});
    }
    for(re int i=1;i<=tot;++i)s[x+px[i]][y+py[i]]=c;
    return 0;
}
int main(){
    n=read(),m=read();
    for(re int i=1;i<=n;++i)scanf("%s",s[i]+1);
    re int ttttt=0;
    while(ck()){
        memset(vis,0,sizeof(vis));
        re int ia=0;
        for(re int i=1;i<=n&&!ia;++i)
            for(re int j=1;j<=m&&!ia;++j)
                if(!vis[i][j]&&s[i][j]!='.'){
                    if(Try(i,j))ia=1;
                }
        if(!ia)return puts("-1"),0;
    }
    printf("%d\n",num);
    for(re int i=num;i;--i){
        printf("%d ",ans1[i]);
        cout<<ans[i]<<'\n';
    }
}