思路
状态矩阵：
题目中的状态是一个 n ∗ m n*m n∗m的矩阵，而一般情况下矩阵快速幂要求用一维向量作为状态矩阵，所以就把这个状态拉成长度为 n ∗ m n*m n∗m的向量了
原矩阵的(i, j) 为状态矩阵中的 F [ ( i − 1 ) ∗ m + j ] F[(i-1)*m + j] F[(i−1)∗m+j]，不妨令 n u m ( i , j ) = ( i − 1 ) ∗ m + j num(i, j) = (i-1)*m + j num(i,j)=(i−1)∗m+j。那么在状态矩阵中就是 F [ n u m ( i , j ) ] F[num(i, j)] F[num(i,j)]了。
另外，令 F [ 0 ] = 1 F[0] = 1 F[0]=1，作为常数1，方便转移出常数。
转移矩阵：
假设ch为原矩阵对应位置i, j对应时刻k的操作：
① 如果ch为"N"，则 A k ( n u m ( i , j ) , n u m ( i − 1 , j ) ) = 1 A_k(num(i, j), num(i-1, j)) = 1 Ak(num(i,j),num(i−1,j))=1; ch 为 “W”、“E”、"S"也是同理。被转移的位置判断一下是否合法。
② 如果ch为[0-9]，则 A k ( 0 , n u m ( i , j ) ) = c h − ′ 0 ′ A_k(0, num(i, j)) = ch-'0' Ak(0,num(i,j))=ch−′0′（加上数值）， A k ( n u m ( i , j ) , n u m ( i , j ) ) = 1 A_k(num(i, j), num(i, j)) = 1 Ak(num(i,j),num(i,j))=1（保留上个状态的值）
③ 保证 F [ 0 ] F[0] F[0]不变， A k ( 0 , 0 ) = 1 A_k(0, 0) = 1 Ak(0,0)=1；
④ A k A_k Ak的其它部分为0。
不同的时刻有不同的转移矩阵，但是由于[1-6]的最小公倍数为60（6为操作序列的最大长度），所以直接处理k = 0-59时刻的所有状态矩阵，然后分解t = q*60 + r（0 ≤ r ＜ 60），
令 A = ∏ k = 0 59 A k ， 则 F t = F 0 ∗ A q ∗ ∏ k = 0 r − 1 A k A=∏_ {k=0}^{59}A_k，则F_t=F_0∗A^q∗∏_{k=0}^{r-1}A_k A=∏k=059Ak，则Ft=F0∗Aq∗∏k=0r−1Ak。
AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_NM = 65;
int n, m, t, act;
string opt[10];
string acts[10];
///F为状态矩阵，A为转移矩阵，A[i][0][0] = 1
ll F[MAX_NM], A[60][MAX_NM][MAX_NM], AAA[MAX_NM][MAX_NM];
inline int num(int i, int j)
{
return (i-1)*m + j;
}
void mul(ll f[MAX_NM], ll a[MAX_NM][MAX_NM])
{
ll c[MAX_NM];
memset(c, 0, sizeof c);
for (int j = 0; j < MAX_NM; j++)
for (int k = 0; k < MAX_NM; k++)
c[j] += f[k] * a[k][j];
memcpy(f, c, sizeof c);
}
void mulb(ll a[MAX_NM][MAX_NM], ll b[MAX_NM][MAX_NM])
{
ll c[MAX_NM][MAX_NM];
memset(c, 0, sizeof c);
for (int i = 0; i < MAX_NM; i++)
for (int j = 0; j < MAX_NM; j++)
for (int k = 0; k < MAX_NM; k++)
c[i][j] += a[i][k]*b[k][j];
memcpy(a, c, sizeof c);
}
void mulself(ll a[MAX_NM][MAX_NM])
{
ll c[MAX_NM][MAX_NM];
memset(c, 0, sizeof c);
for (int i = 0; i < MAX_NM; i++)
for (int j = 0; j < MAX_NM; j++)
for (int k = 0; k < MAX_NM; 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++)
{
///找到格子(i, j)对应的操作序列编号
int index = opt[i-1][j-1] - '0';
///找到对应操作序列在第K秒时候应该执行第几个字符
int indey = k % acts[index].size();
char ch = acts[index][indey];
if (isupper(ch))
{
switch (ch)
{
case 'N':
if (i-1 >= 1)
A[k][num(i, j)][num(i-1, j)] = 1; break;
case 'S':
if (i+1 <= n)
A[k][num(i, j)][num(i+1, j)] = 1; break;
case 'W':
if (j-1 >= 1)
A[k][num(i, j)][num(i, j-1)] = 1; break;
case 'E':
if (j+1 <= m)
A[k][num(i, j)][num(i, j+1)] = 1; break;
case 'D':
A[k][num(i, j)][num(i, j)] = 0;
}
}
if (isdigit(ch))
{
A[k][num(i, j)][num(i, j)] = 1;
A[k][0][num(i, j)] = ch - '0';
}
}
}
}
///初始化为单位矩阵
for (int i = 0; i < MAX_NM; i++)
AAA[i][i] = 1;
for (int k = 0; k < 60; k++)
mulb(AAA, A[k]);
}
int main()
{
cin >> n >> m >> t >> act;
for (int i = 0; i < n; i++)
cin >> opt[i];
for (int i = 0; i < act; i++)
cin >> acts[i];
init();
int q = t/60;
int r = t%60;
for (; q; q >>= 1)
{
if (q&1)
mul(F, AAA);
mulself(AAA);
}
for (int i = 0; i < r; i++)
mul(F, A[i]);
ll ans = 0;
for (int i = 1; i < MAX_NM; i++)
ans = max(ans, F[i]);
cout << ans << endl;
return 0;
}