/*
构造单位矩阵（转移矩阵）
给定n*m网格，每个格子独立按照长度不超过6的操作串循环操作
对应的操作有
0-9：拿x个石头到这个格子
nwse：把这个格子的石头推移到相邻格子
d：清空该格石子
开始时网格是空的，问t秒后石头最多的格子里有多少个石子
t很大，并且每次操作后格子里的石头是线性变化的，所以用矩阵来加速递推
将n*m网格表示成为(i-1)*m+j的一维数组，那么这个数组对应的转移矩阵大小应该是(nm)^2
然后由于每个格子的操作串最长只有6，并且1-6的最小公倍数是60，所以所有格子的操作60秒一个循环
那么求出每秒的转移矩阵，用Ai表示第i秒的转移矩阵，(1<=i<=60)
另A=mul(Ai),t=p*60+r,那么结果状态就是A^p*mul(A1,Ar);
那么如何将操作对应到转移矩阵的构造上？
考虑转移矩阵的运行原理：可以将F'[j]=F[i]*A[i][j]，即将原数组的F[i]*A[i][j]然后加到F'[j]上
0-9：凭空把x个石头转移到第i个格子上，令F[0]=1，A[0][num(i,j)]=x，如此即可完成状态转移
nwse：距离n操作：把第i行的石头转移到第i-1行，即把num[i][j]的石头转移到num[i-1][j]，那么令A[num[i][j]][num[i-1][j]]=1即可
保证要使F[0]=1，那么将A[0][0]设置为1
A的其它数值都为0
F数组就是[1,0,0,0,0,0,0,0,...0]矩阵快速幂加速计算
*/
#include<bits/stdc++.h>
using namespace std;
#define P 65
#define ll long long
int n,m,t,q,i,j,k,x,y,N;
int id[P][P],a[P][P],l[P];
//
char b[P][P];
ll ans;
struct mat{
ll a[P][P];
mat(){memset(a,0,
sizeof a);}
mat operator*(mat b){
//重载矩阵乘法
mat c;
for(
int i=
0;i<n;i++
)
for(
int j=
0;j<n;j++
)
for(
int k=
0;k<n;k++
)
c.a[i][j]+=a[i][k]*
b.a[k][j];
return c;
}
}one,A[P],pre[P],B,C,D;
int main(){
scanf("%d%d%d%d",&n,&m,&t,&
q);
char ch;
for(
int i=
1;i<=n;i++)
//输入每个格子对应的操作序号
for(
int j=
1;j<=m;j++
)
cin>>ch,a[i][j]=ch-
'0',id[i][j]=++
N;
N++
;
for(
int i=
0;i<q;i++){
//输入q行不同的操作序列
scanf(
"%s",b[i]+
1),l[i]=strlen(b[i]+
1);
b[i][0]=b[i][l[i]];
//循环点处理一下
}
for(
int i=
0;i<n;i++)one.a[i][i]=
1;
//构造单位矩阵
pre[
0]=
one;
char c;
for(
int i=
1;i<=
60;i++){
//求出每个时间点对应的状态转移矩阵
A[i].a[
0][
0]=
1;
//对于第1个点
for(
int j=
1;j<=n;j++
)
for(
int k=
1;k<=m;k++
){
//求出第[j,k]块的序号,就是a[j][k]，在第i个时间点对应的操作c
c=b[a[j][k]][i%
l[a[j][k]]];
if(c>=
'0' && c<=
'9'){
//数字
A[i].a[id[j][k]][
0]=c-
'0';
A[i].a[id[j][k]][id[j][k]]++
;
}
if(c==
'N'){
//向各个方向转移
x=j-
1,y=
k;
if(x>=
1)
A[i].a[id[x][y]][id[j][k]]++
;
}
if(c==
'S'){
x=j+
1,y=
k;
if(x<=
n)
A[i].a[id[x][y]][id[j][k]]++
;
}
if(c==
'W'){
x=j,y=k-
1;
if(y>=
1)
A[i].a[id[x][y]][id[j][k]]++
;
}
if(c==
'E'){
x=j,y=k+
1;
if(y<=
m)
A[i].a[id[x][y]][id[j][k]]++
;
}
}
pre[i]=A[i]*pre[i-
1];
//把所有时间点的矩阵乘起来
}
B=pre[
60],C=
one;
for(k=t/
60;k;k>>=
1){
//快速幂
if(k&
1)C=C*
B;
B=B*
B;
}
D.a[0][
0]=
1,D=pre[t%
60]*C*D;
//把余下时间的矩阵呈上去
for(
int i=
1;i<N;i++
)//由于F数组只有第0项为1，那么直接求D[i][0]的最大值即可！
if(ans<D.a[i][
0])
ans=D.a[i][
0];
printf("%lld",ans);
}
转载于:https://www.cnblogs.com/zsben991126/p/10527213.html
