石头游戏

AcWing-206-石头游戏

分析

见《进阶指南》第158页。

实现

#include <iostream>
#include <cctype>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 20, M = 70;
int n, m, t, act;
int a[N][N]; // 网格
char opt[N][N]; // 操作序列
int ptr;
LL b[M][M][M];
int c[N][N];
LL d[M][M];
LL e[M]; // 状态矩阵

int num (int i, int j) {
    return (i - 1) * m + j;
}
void mul (LL a[M][M], LL b[M][M]) {
    LL res[M][M];
    memset(res, 0, sizeof(res));
    for (int i = 0; i <= ptr; ++ i)
        for (int k = 0; k <= ptr; ++ k)
            for (int j = 0; j <= ptr; ++ j)
                res[i][j] += a[i][k] * b[k][j];
    memcpy(a, res, sizeof(res));
}
void mul (LL a[M], LL b[M][M]) {
    LL res[M];
    memset(res, 0, sizeof(res));
    for (int j = 0; j <= ptr; ++ j)
        for (int k = 0; k <= ptr; ++ k)
            res[j] += a[k] * b[k][j];
    memcpy(a, res, sizeof(res));
}

int main () {
    scanf("%d%d%d%d", &n, &m, &t, &act);
    for (int i = 1; i <= n; ++ i) // 网格
        for (int j = 1; j <= m; ++ j)
            scanf("%1d", &a[i][j]);
    for (int i = 0; i < act; ++ i) // 操作序列
        scanf("%s", opt[i]);

    ptr = n * m;
    e[0] = 1;
    for (int k = 1; k <= 60; ++ k) {
        b[k][0][0] = 1;
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= m; ++ j) {
                int x = a[i][j]; // 第 x 个操作序列
                int y = c[i][j]; // 循环指针
                if (isdigit(opt[x][y])) {
                    b[k][0][num(i, j)] = opt[x][y] - '0';
                    b[k][num(i, j)][num(i, j)] = 1;
                }
                if (opt[x][y] == 'N' && i > 1) b[k][num(i, j)][num(i - 1, j)] = 1;
                if (opt[x][y] == 'S' && i < n) b[k][num(i, j)][num(i + 1, j)] = 1;
                if (opt[x][y] == 'W' && j > 1) b[k][num(i, j)][num(i, j - 1)] = 1;
                if (opt[x][y] == 'E' && j < m) b[k][num(i, j)][num(i, j + 1)] = 1;
                c[i][j] = (y + 1) % strlen(opt[x]);
            }
        }
    }
    memcpy(d, b[1], sizeof(b[1]));
    for (int k = 2; k <= 60; ++ k) mul(d, b[k]);

    LL res = 0, k = t / 60;
    while (k > 0) {
        if (k & 1) mul(e, d);
        mul(d, d);
        k /= 2;
    }
    k = t % 60;
    for (int i = 1; i <= k; ++ i) mul(e, b[i]);
    for (int i = 1; i <= ptr; ++ i) res = max(res, e[i]);
    printf("%lld", res);
    return 0;
}