【题解】CF89C Chip Play

7KByte · 2021-04-27 15:57:53 · 题解

首先 n\times m \le 5000，可以知道是个 O(n^2m^2) 可过的题。

估计一下，如果我们枚举起点，然后再对整张棋盘模拟一下，可以得到一个复杂度为 O(n^2m^2) 的算法。

关键在于如何快速模拟这个移动和删除的过程。

不难发现移动就是求前驱和后继，使用双向链表可以快速维护删除，查询和恢复操作。

因为我们的恢复操作是在\rm DFS回溯的时候进行，所以这样做是正确的。

注意链表不仅要维护每一行，还要维护每一列。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 5005
using namespace std;
int n,m;
char s[N][N];
vector<int>up[N],dn[N],lt[N],rt[N];
//int up[N][N],dn[N][N],lt[N][N],rt[N][N];
void del(int x,int y){
    dn[up[x][y]][y]=dn[x][y];
    up[dn[x][y]][y]=up[x][y];
    rt[x][lt[x][y]]=rt[x][y];
    lt[x][rt[x][y]]=lt[x][y];
}
void ins(int x,int y){
    dn[up[x][y]][y]=x;
    up[dn[x][y]][y]=x;
    rt[x][lt[x][y]]=y;
    lt[x][rt[x][y]]=y;
}
int dfs(int x,int y){
    int ans=1;
    if(s[x][y]=='U'){
        int cur=up[x][y];
        if(cur)del(x,y),ans+=dfs(cur,y),ins(x,y);
    }
    else if(s[x][y]=='D'){
        int cur=dn[x][y];
        if(cur!=n+1)del(x,y),ans+=dfs(cur,y),ins(x,y);
    }
    else if(s[x][y]=='L'){
        int cur=lt[x][y];
        if(cur)del(x,y),ans+=dfs(x,cur),ins(x,y);
    }
    else if(s[x][y]=='R'){
        int cur=rt[x][y];
        if(cur!=m+1)del(x,y),ans+=dfs(x,cur),ins(x,y);
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n)scanf("%s",s[i]+1);
    rep(i,0,n+1)up[i].resize(m+3),dn[i].resize(m+3),lt[i].resize(m+3),rt[i].resize(m+3);
    rep(i,1,n){
        int pre=0;
        rep(j,1,m)if(s[i][j]!='.')rt[i][pre]=j,lt[i][j]=pre,pre=j;
        rt[i][pre]=m+1;lt[i][m+1]=pre;
    }
    rep(j,1,m){
        int pre=0;
        rep(i,1,n)if(s[i][j]!='.')dn[pre][j]=i,up[i][j]=pre,pre=i;
        dn[pre][j]=n+1;up[n+1][j]=pre;
    }
    int ans=0,mx=0;
    rep(i,1,n)rep(j,1,m)if(s[i][j]!='.'){
        int cur=dfs(i,j);
        if(cur>mx)mx=cur,ans=1;
        else if(cur==mx)ans++;
    }
    printf("%d %d\n",mx,ans);
    return 0;
}