题目描述

石头游戏在一个 n 行 m 列 (1≤n,m≤8) 的网格上进行，每个格子对应一种操作序列，操作序列至多有10种，分别用0~9这10个数字指明。

操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。

每秒钟，所有格子同时执行各自操作序列里的下一个字符。

序列中的每个字符是以下格式之一：

1、数字0~9：表示拿0~9个石头到该格子。
2、NWSE：表示把这个格子内所有的石头推到相邻的格子，N表示上方，W表示左方，S表示下方，E表示右方。
3、D：表示拿走这个格子的所有石头。

给定每种操作序列对应的字符串，以及网格中每个格子对应的操作序列，求石头游戏进行了 t 秒之后，石头最多的格子里有多少个石头。

在游戏开始时，网格是空的。

样例

in:

1 6 10 3
011112
1E
E
0

out:

3

算法

(矩阵加速) $O(m^3n^3(\log t+60))$

非常套路的矩阵加速题。

因为每一个点的操作周期是不一样的，考虑全部扩大到 $\operatorname{lcm}(1,2,3,4,5,6)=60$。

然后构造 $60$ 个转移矩阵，这样先把所有转移矩阵乘起来转移 $\lfloor\dfrac{t}{60}\rfloor$ 次，剩下的直接暴力乘 $60$ 次就可以了。

题意有一个地方不清楚，就是如果把石头推出棋盘外面（例如最后一行有 S）算作 D 操作。

C++ 代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

inline char readchar() {
    register char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    return c;
}

inline long long Abs(const long long& x) {return (x > 0 ? x : -x);}
inline long long Max(const long long& x, const long long& y) {return (x > y ? x : y);}
inline long long Min(const long long& x, const long long& y) {return (x < y ? x : y);}

struct Matrix {
    int n, m;
    long long a[70][70];
    Matrix() {
        m = n = 0;
        memset(a, 0, sizeof(a));
    }
    inline Matrix operator * (const Matrix& b) const {
        Matrix c;
        c.n = n;
        c.m = b.m;
        for (register int i = 1;i <= n;i++) {
            for (register int j = 1;j <= b.m;j++) {
                for (register int k = 1;k <= m;k++) {
                    c.a[i][j] = c.a[i][j] + a[i][k] * b.a[k][j];
                }
            }
        }
        return c;
    }
};

Matrix Unit(int n) {
    Matrix res;
    res.n = n;
    res.m = n;
    for (register int i = 1;i <= n;i++) res.a[i][i] = 1;
    return res;
}

Matrix Power(Matrix x, long long y) {
    Matrix ans = Unit(x.n);
    while (y) {
        if (y & 1) ans = ans * x;
        x = x * x;
        y >>= 1;
    }
    return ans;
}

char opt[10][10], seq[15][80];
int n, m, t, q, seqtop[15];
Matrix ans, trans[65];

inline void Read() {
    n = qread(); m = qread(); t = qread(); q = qread();
    for (register int i = 1;i <= n;i++) {
        for (register int j = 1;j <= m;j++) opt[i][j] = readchar();
    }
    for (register int i = 1;i <= q;i++) {
        register char c = getchar();
        while ((c < '0' || c > '9') && c != 'N' && c != 'W' && c != 'S' && c != 'E' && c != 'D') c = getchar();
        while ((c >= '0' && c <= '9') || c == 'N' || c == 'W' || c == 'S' || c == 'E' || c == 'D') {
            seq[i][++seqtop[i]] = c;
            c = getchar();
        }
        //printf("i=%d\n", i);
    }
}

inline void Solve() {
    //puts("qwq");
    for (register int i = 1;i <= q;i++) {
        for (register int j = 1;j <= 60;j++) seq[i][j] = seq[i][(j - 1) % seqtop[i] + 1];
    }
    for (register int i = 1;i <= 60;i++) {
        trans[i].n = trans[i].m = n * m + 1;
        trans[i].a[1][1] = 1;
        for (register int j = 1;j <= n;j++) {
            for (register int k = 1;k <= m;k++) {
                const char& o = seq[opt[j][k] - '0' + 1][i];
                if (o >= '0' && o <= '9') {
                    trans[i].a[1][(j - 1) * m + k + 1] += o - '0';
                    trans[i].a[(j - 1) * m + k + 1][(j - 1) * m + k + 1] = 1;
                }
                else if (o == 'N' && j != 1) trans[i].a[(j - 1) * m + k + 1][(j - 2) * m + k + 1]++;
                else if (o == 'S' && j != n) trans[i].a[(j - 1) * m + k + 1][j * m + k + 1]++;
                else if (o == 'W' && k != 1) trans[i].a[(j - 1) * m + k + 1][(j - 1) * m + k]++;
                else if (o == 'E' && k != m) trans[i].a[(j - 1) * m + k + 1][(j - 1) * m + k + 2]++;
            }
        }
    }
    trans[0] = trans[1];
    for (register int i = 2;i <= 60;i++) trans[0] = trans[0] * trans[i];
    ans.n = 1;
    ans.m = n * m + 1;
    ans.a[1][1] = 1;
    ans = ans * Power(trans[0], t / 60);
    for (register int i = 1;i <= t % 60;i++) {
        ans = ans * trans[i];
        // for (register int i = 1;i <= ans.m;i++) {
        //  printf("%lld ", ans.a[1][i]);
        // }
        // puts("");
    }
    register long long _ans = 0;
    for (register int i = 2;i <= ans.m;i++) {
        //printf("%lld ", ans.a[1][i]);
        _ans = Max(_ans, ans.a[1][i]);
    }
    //puts("");
    printf("%lld", _ans);
}

int main() {
    Read();
    Solve();
    #ifndef ONLINE_JUDGE
    while (1);
    #endif
    return 0;
}