思路

首先，如果硬模拟，由于 $t \le 10^8$，会超时。

考虑到矩阵快速幂，由于操作长度小于等于 $6$，可以得到 $60$ 秒钟过后必有一个循环节。

有了这个性质过后，我们可以考虑把 $t$ 划分成 $t \div 60$ 下取整个完整的循环节和 $t \bmod 60$ 的余下的。

我们可以用一个 $n\times m$ 的向量，记能使 $i-1$ 秒转移到 $i$ 秒的 矩阵为 $a_i$，这里 $1\le i\le60$。

然后我们令 $A = \Pi_{i=1}^{60} a_i$，令 $t=60q+r$，且 $r \le 60$，那么我们答案为 $f_0 \times A^q \times \Pi_{i=1}^{r}a_i$。

这是基本大方向，但是具体细节在于如何求出变换矩阵 $a_i$。

每次乘的矩阵的边长为 $n\times m$，对于矩阵 $a_{time}$，这里是求法：

$a_{time,0,0}=1$。

对于任意 $(i,j)$，他在 $time$ 秒钟的操作符号记为 $op$，则：

若 $op$ 为数字，则 $a_{time,0,get(i,j)}=op$，$a_{time,get(i,j),get(i,j)}=1$，这里 $get$ 返回的是 $(i - 1) \times m + j$。

若 $op$ 为 N，则当 $i > 1$ 成立时，$a_{time,get(i,j),get(i - 1,j)} = 1$。

若 $op$ 为 S，则当 $i < n$ 成立时，$a_{time,get(i,j),get(i + 1,j)} = 1$。

若 $op$ 为 W，则当 $j > 1$ 成立时，$a_{time,get(i,j),get(i,j - 1)} = 1$。

若 $op$ 为 E，则当 $j < m$ 成立时，$a_{time,get(i,j),get(i,j + 1)} = 1$。

如果都没有被赋值的地方，为 $0$。

然后求出来过后按照上面的公式计算即可。

代码

#include <bits/stdc++.h>
using namespace std;
long long n,m,t,k;
long long a[62][70][70];
long long tmp[70][70];
long long fc[70][70];
long long checker[70][70];
string op[70]; 
void mul_qmi(long long f[70],long long a[70][70]){
    long long c[70];
    memset(c,0,sizeof c);
    for (long long i = 0; i <= n * m; i ++ ){
        for (long long j = 0 ;j <= n * m; j ++ ){
            c[i] = (c[i] + (long long)f[j] * a[j][i]);
        }
    }
    memcpy(f,c,sizeof c);
}
void mul_qmi2(long long a[70][70]){
    long long c[70][70];
    memset(c,0,sizeof c);
    for (long long i = 0; i <= n * m; i ++ ){
        for (long long j = 0; j <= n * m; j ++ ){
            for (long long k = 0; k <=  n * m; k ++ ){
                c[i][j] = (c[i][j] + (long long)a[i][k] * a[k][j]);
            }
        }
    }
    memcpy(a,c,sizeof c);
}
void mul(long long a[70][70],long long b[70][70]){
    long long c[70][70];
    memset(c,0,sizeof c);
    for (long long i = 0; i <= n * m; i ++ ){
        for (long long j = 0; j <= n * m; j ++ ){
            for (long long k = 0; k <=  n * m; k ++ ){
                c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]);
            }
        }
    }
    memcpy(a,c,sizeof c);
}
long long get(long long x,long long y){
    return (x - 1) * m + y;
}
void qmi(){
    long long f[70];
    memset(f,0,sizeof f);
    cin >> n >> m >> t >> k;
    for (long long i =1; i <= n; i ++ ){
        for(long long j =1; j <= m; j ++ ){
            char x;
            cin >> x;
            fc[i][j] = x - '0';
        }
    }
    for (long long i = 0; i < k; i ++ ){
        cin >> op[i];
    }
    for (long long T = 1; T <= 60; T ++ ){
        a[T][0][0] = 1;
        for (long long i = 1; i <= n; i ++ ){
            for (long long j = 1; j <= m; j ++ ){
                long long t = checker[i][j];
                if (op[fc[i][j]][t] >= '0' && op[fc[i][j]][t] <= '9'){
                    a[T][0][get(i,j)] = op[fc[i][j]][t] - '0';
                    a[T][get(i,j)][get(i,j)] = 1;
                }
                else if (op[fc[i][j]][t] == 'N' && i > 1){
                    a[T][get(i,j)][get(i - 1,j)] = 1;
                }
                else if (op[fc[i][j]][t] == 'S' && i < n){
                    a[T][get(i,j)][get(i + 1,j)] = 1;
                }
                else if (op[fc[i][j]][t] == 'W' && j > 1){
                    a[T][get(i,j)][get(i,j - 1)] = 1;
                }
                else if (op[fc[i][j]][t] == 'E' && j < m){
                    a[T][get(i,j)][get(i,j + 1)] = 1;
                }
                checker[i][j] = (t + 1) % (op[fc[i][j]].size()); 
            }
        }
    }
    for (long long i = 0; i <= n *m ; i ++ ){
        for (long long j = 0; j <= n * m; j ++ ){
            tmp[i][j] = a[1][i][j];
        }
    }
    for (long long i = 2;i <= 60; i ++ ){
        mul(tmp,a[i]);
    }
    f[0] = 1;
    long long check = t / 60;
    while (check){
        if (check & 1){
            mul_qmi(f,tmp);
        }
        mul_qmi2(tmp);
        check >>= 1;
    }
    for (long long i = 1; i <= t % 60; i ++ ){
        mul_qmi(f,a[i]);
    }
    long long res = 0;
    for (long long i = 1; i <= n * m; i ++ ){
        res = max(res,f[i]);
    }
    cout << res;
}
int main(){
    qmi();
    return 0;
}