acwing 206题解

具体b站有.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=65;
int n,m,t,acts;//代表n行m列.t时间,act个操作
string ops[10];
string act[10];
ll F[N],A[N][N][N],AA[N][N];
int num(int x,int y) { return (x-1)*m+y; }
void mul(ll f[N],ll a[N][N])
{
    ll c[N];
    memset(c,0,sizeof c);
    for(int j=0;j<N;j++)
    {
        for(int k=0;k<N;k++)
        {
            c[j]+=a[k][j]*f[k];
        }
    }
    memcpy(f,c,sizeof c);
}

void mulb(ll a[N][N],ll b[N][N])
{
    ll c[N][N];
    memset(c,0,sizeof c);
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {
                c[i][j]+=a[i][k]*b[k][j];
            }
        }
    }
    memcpy(a,c,sizeof c);
}

void mulself(ll a[N][N]) 
{
    ll c[N][N];
    memset(c,0,sizeof c);
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {
                c[i][j]+=a[i][k]*a[k][j];
            }
        }
    }
    memcpy(a,c,sizeof c);
}

void init()
{
    F[0]=1;
    for(int k=0;k<60;k++)
    {
        A[k][0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int idx=ops[i-1][j-1]-'0';
                int idy=k%act[idx].size();
                char ch=act[idx][idy];
                if(ch=='N')
                {
                    if(i-1>=1) A[k][num(i,j)][num(i-1,j)]=1;
                }
                else if(ch=='S')
                {
                    if(i+1<=n) A[k][num(i,j)][num(i+1,j)]=1;
                }
                else if(ch=='E')
                {
                    if(j+1<=m) A[k][num(i,j)][num(i,j+1)]=1;
                }
                else if(ch=='W')
                {
                    if(j-1>=1) A[k][num(i,j)][num(i,j-1)]=1;
                }
                else if(ch=='D')
                {
                    A[k][num(i,j)][num(i,j)]=0;
                }
                else
                {
                    A[k][num(i,j)][num(i,j)]=1;
                    A[k][0][num(i,j)]=ch-'0';
                }
            }
        }
    }
    for(int i=0;i<N;i++)
    {
        AA[i][i]=1;
    }
    for(int k=0;k<60;k++)
    {
        mulb(AA,A[k]);
    }
}

int main()
{
    cin>>n>>m>>t>>acts;
    for(int i=0;i<n;i++) cin>>ops[i];
    for(int i=0;i<acts;i++) cin>>act[i];
    init();//预处理下60.
    int q=t/60;
    int r=t%60;
    while(q)
    {
        if(q&1) mul(F,AA);
        mulself(AA);
        q>>=1;
    }
    for(int i=0;i<r;i++)
    {
        mul(F,A[i]);
    }
    ll ans=0;
    for(int i=1;i<N;i++)
    {
        ans=max(ans,F[i]);
    }
    cout<<ans<<endl;
    return 0;
}