#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
inline int sum(int i,int j){
	return (i-1)*m+j;
}
char tp[10][10];
string op[15];
int siz[15];
struct matrix{
	ll t[70][70];
	matrix(){
		memset(t,0,sizeof t);
		for(int i=0;i<=n*m;i++)t[i][i]=1;
	}
};
matrix operator*(const matrix&a,const matrix&b){
	matrix c;
	for(int i=0;i<=n*m;i++)c.t[i][i]=0;
	for(int i=0;i<=n*m;i++)
		for(int j=0;j<=n*m;j++)
			for(int k=0;k<=n*m;k++)
				c.t[i][j]+=a.t[i][k]*b.t[k][j];
	return c;
}
matrix qpow(matrix a,int k){
	matrix res;
	for(;k;k>>=1){
		if(k&1)res=res*a;
		a=a*a;
	}
	return res;
}
int main(){
	int t,act;
	cin>>n>>m>>t>>act;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>tp[i][j];
		}
	for(int i=0;i<act;i++){cin>>op[i];siz[i]=op[i].size();}
	matrix a,b;
	for(int k=0;k<60;k++){
		matrix r;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				char now=op[tp[i][j]-'0'][k%siz[tp[i][j]-'0']];
				int w=sum(i,j);
				if(isdigit(now)){
					r.t[0][w]=now-'0';
				}else{
					int x;
					switch(now){
						case 'E':x=sum(i,j+1);break;
						case 'N':x=sum(i-1,j);break;
						case 'S':x=sum(i+1,j);break;
						case 'W':x=sum(i,j-1);break;
						case 'D':x=w;break;
					}
					r.t[w][x]=1;r.t[w][w]=0;
				}
			}
		a=a*r;
		if(k<t%60)b=b*r;
	}
	a=qpow(a,t/60);
	a=a*b;
	ll ans=0;
	for(int i=1;i<=n*m;i++){
		ans=max(a.t[0][i],ans);
	}
	cout<<ans<<"\n";
	return 0;
}

一组WA数据

8 8 100000000 10
13983779
56620380
91254988
20656288
43363525
67824559
93351733
15817451
5EE8
7
37S
S4
85N5S
D
5DD1
7E9N8S
5E0
9