自动搬运

查看原文

来自洛谷，原作者为

	wosile 疑罪从无。

搬运于2025-08-24 21:16:23，当前版本为作者最后更新于2024-06-05 11:13:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

UPD：修正笔误。

信息与未来真神吧？拿这种东西给小学生做？

我的做法可能偏复杂了。

观察到 $n,m \le 10$，对于每对括号，我们可以先对于其内部的字符串，计算出对于每一种初始位置，经过这个字符串后可能会到达哪里，以及可能会经过哪些位置。这两个信息可以用两个大小为 $nm \times nm$ 的 $\texttt{01}$ 矩阵 $M_t,M_p$ 表示。也就是说，一段字符串 $S$ 就可以转化成一个矩阵二元组 $(M_t,M_p)$。

对于单个字符 LRUD，我们可以提前把它们对应的这两个矩阵算出来。

方便起见，我们把全部 $nm$ 个位置从 $1$ 到 $nm$ 编号，比如说，$S(M_t,M_p)$ 中，$M_p(x,y)$ 就代表从编号为 $x$ 的位置开始，经过字符串 $S$ 所代表的操作序列，有没有可能经过编号为 $y$ 的位置。

当两段操作序列 $S(M_t,M_p),T(N_t,N_p)$ 按顺序拼接在一起得到 $ST(F_t,F_p)$ 时，假如我们从 $x$ 号位置开始，我们会先经过 $M_p(x,t)=1$ 的位置 $t$，然后到达 $M_t(x,r)=1$ 的位置 $r$，然后再经过 $N_p(r,z)=1$ 的位置 $z$，到达 $N_t(r,y)=1$ 的位置 $y$。

由此并不显然有，$F_t(x,y)=\bigcup\limits_{r=1}^{nm}(M_t(x,r)\cap N_t(r,y))$ 和 $F_p(x,y)=(\bigcup \limits_{r=1}^{nm}M_t(x,r)\cup N_p(r,y))\cup M_p(x,y)$。

我们发现这个东西很像矩阵乘法。具体来讲，若乘法为 $\text{and-or}$ 矩阵乘法，那么 $F_t=M_t\times N_t$，$F_p=M_p \cup (M_t \times N_p)$。显然是有结合律的，那不妨定义矩阵二元组的乘法如上，即 $(M_t,M_p)(N_t,N_p)=(M_tN_t,M_tN_p\cap M_p)$。

做这个乘法的复杂度是 $O(n^3m^3)$ 的，但是我们可以通过 std::bitset 或者 unsigned long long 或者 __int128 之类的东西压位，可以做到 $O(\frac{n^3m^3}{w})$。

对于 $\texttt{(S)k}$ 的情况，显然整个字符串对应的矩阵二元组就是 $k$ 个 $S(M_t,M_p)$ 相乘，即 $(F_t,F_p)=(M_t,M_p)^k$。这里可以用快速幂，当然不用也无所谓。

对于 $\texttt{(S)*}$ 的情况，若把 $M_t$ 看作一个邻接矩阵，则 $F_t$ 相当于一个可达性矩阵，而 $F_p(x,y)$ 则相当于“在这个图上从 $x$ 号位置开始走能到达的所有点 $t$ 中，是否有点满足 $M_p(t,y)=1$”。$F_t$ 可以通过 Floyd-Warshall 传递闭包（这里也可以压位除掉一个 $w$）求出，$F_p$ 可以一并求出。

然后全拼起来就做完了，总复杂度 $O(\frac{n^3m^3|S|k}w)$，其中 $k$ 是括号后附带的数字，$k \le 9$。如果你有心情做矩阵快速幂可以做到 $O(\frac{n^3m^3|S|\log k}w)$，常数非常小。

这题既不入门，也不面试，但是它在入门与面试题库里面。综合算法难度，思维难度和代码难度，我觉得这应该是 B 题库最难的一题。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
char s[15][15],S[1005];
int n,m,N;
inline int id(int x,int y){
    return (x-1)*m+y;
}
inline int getx(int x){
    return (x-1)/m+1;
}
inline int gety(int x){
    return (x-1)%m+1;
}
struct command{
    command(){
        for(int i=1;i<=N;i++){
            to[i].reset();
            path[i].reset();
        }
    }
    bitset<105>to[105],path[105];
    void operator |=(command o){
        for(int i=1;i<=N;i++){
            to[i]|=o.to[i];
            path[i]|=o.path[i];
        }
    }
}com[505];
int cnt=0,readpos=0;
bitset<105>tr[105];
command concatenate(const command &x,const command &y){
    command z;
    for(int i=1;i<=N;i++)z.path[i]=x.path[i];
    for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)if(x.to[i][j]){
        z.to[i]|=y.to[j],z.path[i]|=y.path[j];
    }
    return z;
}
command repeat(command &x,int k){
    for(int i=1;i<=N;i++)tr[i].reset();
    command ans;
    for(int i=1;i<=N;i++)ans.to[i][i]=1,ans.path[i][i]=1;
    if(k<1 || k>9){
        ans|=x;
        for(int i=1;i<=N;i++)for(int j=1;j<=N;j++){
            // Floyd 求最短路的时候我们有 dis[j][k] <--- dis[j][i]+dis[i][k]，这里也是一样的道理。
            if(ans.to[j][i]){
                ans.to[j]|=ans.to[i];
                ans.path[j]|=ans.path[i];
            }
        }
    }
    else{
        command tmp=x;
        while(k){
            // 快速幂
            if(k&1)ans=concatenate(ans,tmp);
            tmp=concatenate(tmp,tmp);
            k>>=1;
        }
    }
    return ans;
}
int Len;
void walk(command &x,int dir){
    for(int i=1;i<=N;i++)tr[i].reset();
    for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)if(x.to[i][j]){
        int nx=getx(j)+dx[dir],ny=gety(j)+dy[dir];
        if(nx>=1 && nx<=n && ny>=1 && ny<=m && s[nx][ny]=='.')tr[i][j+dx[dir]*m+dy[dir]]=1;
        else tr[i][j]=1;
    }
    for(int i=1;i<=N;i++)x.to[i]=tr[i],x.path[i]|=tr[i];
}
void readCommand(command &x){
    for(int i=1;i<=N;i++){
        x.to[i][i]=x.path[i][i]=1;
    }
    while(readpos<Len && S[readpos]!=')'){
        char c=S[readpos];
        // LRUD 可以做到 N^2 而不是 N^3/w
        if(c=='L')walk(x,0);
        if(c=='R')walk(x,1);
        if(c=='U')walk(x,2);
        if(c=='D')walk(x,3);
        if(c=='('){
            ++readpos;
            command &f=com[++cnt];
            readCommand(f);
            ++readpos;
            char op=S[readpos];
            x=concatenate(x,repeat(f,op-48));
        }
        ++readpos;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    N=n*m;
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    scanf("%s",S);
    Len=strlen(S);
    readCommand(com[++cnt]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#')putchar('#');
            else if(com[1].path[id(1,1)][id(i,j)])putchar('+');
            else putchar('.');
        }
        putchar('\n');
    }
    return 0;
}