题解：P4621 [COCI2012-2013#6] BAKTERIJE

· · 题解

P4621 BAKTERIJE

题意略。

注意到细菌的数量相当少，因此我们逐个细菌进行考虑。对于单个细菌而言，如果将每个位置的四个朝向分别视为一个节点，那么每个节点会移动向唯一的另一个节点，那么也就构成了一个内向基环树森林。

于是，由于数据范围很小，所以如果我们希望求出到某一个点的步数，在环外的部分我们可以暴力跳，每跳一步就判断一次是否满足答案，跳到环上之后就构成一个循环。

注意到终点并不是唯一的，陷阱位置四个方向对应的节点都可以作为终点，但是可以直接 4^k 强行枚举每个细菌到达的究竟是哪个终点。然后在多个细菌的情况下，我们可以先暴力跳直到所有细菌都在环上，这样每个细菌的出现位置都构成了一个循环，然后注意到这是一个同余方程组的形式，于是可以直接使用扩展中国剩余定理求解。

一些实现上的注意事项：

  1. 方程组求解完后，如果步数小于跳到环上的步数，要加上若干最小公倍数直到不小于跳到环上的步数。
  2. 陷阱消灭细菌需要消耗一秒时间，所以最后答案还要加一。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
int n,m,k,x,y,to[10][N];
char c[4]={'U','R','D','L'};
int getid(int i,int j,char c){
    int ans=4*((i-1)*m+j-1);
    if(c=='U')return ans+1;
    else if(c=='R')return ans+2;
    else if(c=='D')return ans+3;
    return ans+4;
}
bool vis[10][N],flg[10][N];
int pos[N],a[10][55][55];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int siz[10][N],fa[10][N];
int find(int i,int x){
    return fa[i][x]==x?x:fa[i][x]=find(i,fa[i][x]);
}
void unionn(int i,int a,int b){
    int x=find(i,a),y=find(i,b);
    if(x==y)return;
    fa[i][x]=y;
}
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y),_x=x,_y=y;
    x=_y;
    y=_x-(a/b)*_y; 
    return d;
}
int A[N],B[N];
int excrt(int n,int p){
    int lcm=A[1],ans=B[1];
    for(int i=2;i<=n;++i){
        int x,y;
        B[i]=((B[i]-ans)%A[i]+A[i])%A[i];
        int d=exgcd(lcm,A[i],x,y);
        if(B[i]%d)return 1e18;
        x=B[i]/d*x%A[i];
        A[i]/=d;
        ans=ans+x*lcm;
        lcm=lcm*A[i];
        ans=(ans%lcm+lcm)%lcm;
    }
    if(ans<p)ans=(p-ans+lcm-1)/lcm*lcm+ans;
    return ans;
}
int st[N];
int ed[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k>>x>>y;
    for(int i=1;i<=4*n*m;++i)for(int j=1;j<=k;++j)fa[j][i]=i;
    for(int i=1;i<=k;++i){
        int x,y;char z;
        cin>>x>>y>>z;
        pos[i]=getid(x,y,z);
        for(int j=1;j<=n;++j){
            for(int p=1;p<=m;++p){
                char c;
                cin>>c;
                a[i][j][p]=c-'0';
            }
        }
    }
    int tot=4*n*m;
    for(int o=1;o<=k;++o){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                for(int p=0;p<=3;++p){
                    int nxt=(p+a[o][i][j])%4;
                    if(nxt==0&&i==1)nxt=2;
                    if(nxt==3&&j==1)nxt=1;
                    if(nxt==1&&j==m)nxt=3;
                    if(nxt==2&&i==n)nxt=0;
                    to[o][getid(i,j,c[p])]=getid(i+dx[nxt],j+dy[nxt],c[nxt]);
                    unionn(o,getid(i,j,c[p]),getid(i+dx[nxt],j+dy[nxt],c[nxt]));
                }
            }
        }
    }
    for(int j=1;j<=k;++j){
        for(int i=1;i<=tot;++i){
            if(!vis[j][find(j,i)]){
                int now=i;
                while(!vis[j][now]){
                    vis[j][now]=1;
                    now=to[j][now];
                }
                if(flg[j][now])continue;
                vis[j][find(j,i)]=1;
                int tmp=now;
                do{
                    flg[j][tmp]=1;
                    siz[j][find(j,now)]++;
                    tmp=to[j][tmp];
                }while(tmp!=now);
            }
        }
    }
    int ans=1e18;
    for(int i=0;i<(1<<2*k);++i){
        int cnt=0,cnt2=0,tim=0;
        for(int j=1;j<=k;++j)st[j]=pos[j];
        for(int j=0;j<k;++j)ed[j+1]=(i>>(j*2)&1)*2+(i>>(j*2+1)&1);
        for(int j=1;j<=k;++j)ed[j]=getid(x,y,c[ed[j]]);
        for(int j=1;j<=k;++j)if(flg[j][st[j]])cnt++;
        for(int j=1;j<=k;++j)if(st[j]==ed[j])cnt2++;
        if(cnt2==k){
            cout<<1;
            return 0;
        }
        while(cnt!=k){
            for(int j=1;j<=k;++j)if(st[j]==ed[j])cnt2--;
            cnt=0;
            for(int j=1;j<=k;++j)st[j]=to[j][st[j]];
            for(int j=1;j<=k;++j)if(flg[j][st[j]])cnt++;
            for(int j=1;j<=k;++j)if(st[j]==ed[j])cnt2++;
            tim++;
            if(cnt2==k)ans=min(ans,tim);
        }
        bool tmp=0,tmp2=0;
        for(int j=1;j<=k;++j){
            if(!flg[j][ed[j]])tmp=1;
            if(find(j,st[j])!=find(j,ed[j]))tmp2=1;
        }
        if(tmp||tmp2)continue;
        for(int j=1;j<=k;++j){
            B[j]=tim;
            A[j]=siz[j][find(j,st[j])];
            int now=st[j];
            while(now!=ed[j]){
                now=to[j][now];
                B[j]++;
            }
            B[j]%=A[j];
        }
        ans=min(ans,excrt(k,tim));
    }
    if(ans==1e18)ans=-2;
    cout<<ans+1;
    return 0;
}