记录编号	584993	评测结果	AAAAAA
题目名称	石头游戏	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2023-11-17 20:18:17	内存使用	6.63 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 12;
typedef long long ll;
ll n,m,k,q;
struct Matrix{
    ll a[66][66],n,m;
    void clear(){n = m = 0;memset(a,0,sizeof(a));}
    Matrix operator * (const Matrix x)const{
        Matrix y;y.clear();
        y.n = n,y.m = m;
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++)
                for(int k = 1;k <= m;k++)
                    y.a[i][j] = (y.a[i][j] + (a[i][k] * x.a[k][j]));
        return y;
    }
}c[66],f;
char op[N][N];
ll l[N],a[N][N];
ll id(ll x,ll y){
    return (x-1)*n+y;
}// 
int main(){
    freopen("marble.in","r",stdin);
    freopen("marble.out","w",stdout);
    scanf("%lld%lld%lld%lld",&n,&m,&k,&q);
    f.n = 1,f.m = n*m+1;
    f.a[1][n*m+1] = 1;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++){
            char ch;cin>>ch;
            a[i][j] = ch - '0';// 
        }
    for(int i = 0;i < q;i++)scanf("%s",op[i]+1),l[i] = 1;
    //操作序列为6,1~6的最小公倍数为60，则可以以60为分界 
    for(int k = 1;k <= 60;k++){
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                int u = a[i][j];
                char w = op[u][l[u]];
                if(w >= '0' && w <= '9')c[k].a[n*m+1][id(i,j)] = w - '0',c[k].a[id(i,j)][id(i,j)] = 1;//自己！！ 
                else if(w == 'E' && j < m)c[k].a[id(i,j)][id(i,j+1)] = 1;
                else if(w == 'W' && j > 1)c[k].a[id(i,j)][id(i,j-1)] = 1;
                else if(w == 'N' && i > 1)c[k].a[id(i,j)][id(i-1,j)] = 1;
                else if(w == 'S' && i < n)c[k].a[id(i,j)][id(i+1,j)] = 1;
            }
        }//c[k]表示前k秒操作的转移矩阵 
        for(int i = 0;i < q;i++){
            if(l[i] + 1 > strlen(op[i]+1))l[i] = 1;
            else l[i]++;
        }//
        c[k].a[n*m+1][n*m+1] = 1;//常数1 
        c[k].n = c[k].m = n*m+1;
        if(k != 1)c[k] = c[k-1] * c[k];//前缀乘，不满足交换律 
    }
    ll u = k / 60;
    while(u){
        if(u & 1)f = f * c[60];
        c[60] = c[60] * c[60];
        u >>= 1;
    }
    u = k % 60;
    if(u)f = f * c[u];// 
    ll ans = 0;
    for(int i = 1;i <= n*m;i++)ans = max(f.a[1][i],ans);
    printf("%lld\n",ans);
    
    return 0;
    
}