毒瘤思路
对，这道题是毒瘤题。首先，我们可以判定出，这些序列一定会在\(60s\)内全部从头开始，因为\(1,2,3,4,5,6\)的最大公倍数为\(60\)。之后，我们可以考虑把这些操作放入操作矩阵之中。操作矩阵的长宽都为\(n*m\)。具体的操作对应如下：
- 在本题中，我们把一个二维的点映射为一个数，公式为\(num(i,j)=(i-1)m+j\)。
- 对于把格子值设置为数字的操作：
- 首先把操作矩阵\(A[0][num(i,j)]\)设置为操作数。
- 之后，把矩阵\(A[num(i,j)][num(i,j)]\)设置为\(1\)，这是为了使其在矩阵乘法中得到保留。
- 而对于移动操作：
- 如果是\(E\)，那么把\(A[num(i,j)][num(i,j+1)]\)设置为一，以此类推
- …
然后算出\(p=\lfloor \frac{m}{60} \rfloor, q = m \mod 60\)，进行矩阵快速幂和连续乘法即可。
好毒瘤，建议不要写。
代码
// CH3401.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 70;
ll N, M, t, act;
char opt[MAX_N][MAX_N];
string opts[MAX_N];
struct matrix
{
ll mat[MAX_N][MAX_N], n, m;
matrix() { memset(mat, 0, sizeof(mat)); }
matrix(int n, int m)
{
this->n = n, this->m = m;
for (int i = 1; i <= max(n, m); i++)
mat[i][i] = 1;
}
matrix operator*(const matrix &tar) const
{
matrix ans = matrix();
ans.n = n, ans.m = tar.m;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= tar.m; j++)
for (int k = 0; k <= m; k++)
ans.mat[i][j] += mat[i][k] * tar.mat[k][j];
return ans;
}
matrix operator^(const int &tim) const
{
int ti = tim;
matrix ans, bas = *this;
for (int i = 0; i <= max(n, m); i++)
ans.mat[i][i] = 1;
ans.n = n, ans.m = m;
while (ti)
{
if (ti & 1)
ans = ans * bas;
bas = bas * bas;
ti >>= 1;
}
return ans;
}
} P, Q, mats[70];
ll getPos(ll x, ll y) { return (x - 1) * M + y; }
int main()
{
scanf("%lld%lld%lld%lld", &N, &M, &t, &act);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> opt[i][j], opt[i][j] -= '0';
for (int i = 0; i < act; i++)
cin >> opts[i];
int p = t / 60, q = t % 60;
matrix F;
F.n = 0, F.m = getPos(N, M), F.mat[0][0] = 1;
for (int tim = 1; tim <= 60; tim++)
{
matrix current;
current.n = getPos(N, M), current.m = getPos(N, M);
current.mat[0][0] = 1;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
{
int pos = (tim - 1) % (opts[opt[i][j]].size());
char op = opts[opt[i][j]][pos];
switch (op)
{
case 'N':
if (i > 1)
current.mat[getPos(i, j)][getPos(i - 1, j)] = 1;
break;
case 'S':
if (i < N)
current.mat[getPos(i, j)][getPos(i + 1, j)] = 1;
break;
case 'E':
if (j < M)
current.mat[getPos(i, j)][getPos(i, j + 1)] = 1;
break;
case 'W':
if (j > 1)
current.mat[getPos(i, j)][getPos(i, j - 1)] = 1;
break;
case 'D':
break;
default:
current.mat[0][getPos(i, j)] = op - '0';
current.mat[getPos(i, j)][getPos(i, j)] = 1;
break;
}
}
mats[tim] = current;
}
P = mats[1];
for (int i = 2; i <= 60; i++)
P = P * mats[i];
P = P ^ p;
Q = q == 0 ? matrix(getPos(N, M), getPos(N, M)) : mats[1];
for (int i = 2; i <= q; i++)
Q = Q * mats[i];
F = F * P * Q;
ll ans = 0;
for (int i = 1; i <= getPos(N, M); i++)
ans = max(ans, F.mat[0][i]);
printf("%lld", ans);
return 0;
}
