[数据结构与算法]206. 石头游戏(矩阵快速幂)（未找出bug。。。）

传送门

#include<bits/stdc++.h>
#include<cstdio>
#include<queue>
#include<set>
#include<cstdlib>
#include<string.h>
#include<string>
#include<iostream>
#include<cmath>
#include<map>
#include<algorithm>
#define endl "\n"
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define ft first
#define sd second
#define pll pair<ll, ll>
#define pii pair<int, int>
//#define ll long long int
#define ull unsigned long long int
#define mt(a,b) memset(a, b, sizeof a)
#define int long long
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int INF = 0x7fffffff;
using namespace std;
const int N = 2e5 + 7, M = 1e6 + 10;
int n, m;
char order[100][100];
string s[200];
int f[100];
int a[100][100][100], b[100][100];

int num(int i, int j)
{
	return (i - 1) * m + j;
}

void mul(int f[100], int a[100][100])
{
	int c[100];
	mt(c, 0);
	for (int j = 0; j <= 90; j++)
		for (int k = 0; k <= 90; k++)
			c[j] = c[j] + f[k] * a[k][j];
	memcpy(f, c, sizeof c);
}

void mulself(int a[100][100], int b[100][100])
{
	int c[100][100];
	mt(c, 0);
	for (int i = 0; i <= 90; i++)
		for (int j = 0; j <= 90; j++)
			for (int k = 0; k <= 90; k++)
				c[i][j] = c[i][j] + a[i][k] * b[k][j];
	memcpy(a, c, sizeof c);
}

unsigned main()
{
	IOS;
	int n, m, t, act;
	cin >> n >> m >> t >> act;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> order[i][j];
	for (int i = 0; i < act; i++)
		cin >> s[i];


	for (int k = 0; k < 60; k++)
	{
		
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				int idx = order[i][j] - '0';

				char ch = s[idx][k % s[idx].size()];
				if (isdigit(ch)) a[k][0][num(i, j)] = ch - '0', a[k][num(i, j)][num(i, j)] = 1;
				else if (ch == 'N' && i > 1) a[k][num(i, j)][num(i - 1, j)] = 1;
				else if (ch == 'W' && j > 1) a[k][num(i, j)][num(i, j - 1)] = 1;
				else if (ch == 'S' && i < n) a[k][num(i, j)][num(i + 1, j)] = 1;
				else if (ch == 'E' && j < m) a[k][num(i, j)][num(i, j + 1)] = 1;
			}
		a[k][0][0] = 1;
	}

	int times = t / 60;
	memcpy(b, a[0], sizeof a[0]);
	//for (int i = 0; i <= m * n; i++) b[i][i] = 1;//单位矩阵
	for (int i = 1; i < 60; i++)
		mulself(b, a[i]);

	f[0] = 1;
	for (; times; times >>= 1)
	{
		if (times & 1) mul(f, b);
		mulself(b, b);
	}

	int r = t % 60;
	//for (int i = 0; i <= m * n; i++) b[i][i] = 1;//单位矩阵
	memcpy(b, a[0], sizeof a[0]);
	for (int i = 1; i < r; i++)
		mulself(b, a[i]);
	mul(f, b);
	//for (int i = 0; i <= m * n; i++)
	//{
	//	for (int j = 0; j <= m * n; j++)
	//		cout << b[i][j] << " ";
	//	cout << "\n";
	//}

	//for (int k = 0; k < 60; k++)
	//{
	//	for (int i = 0; i <= n * m; i++)
	//	{
	//		for (int j = 0; j <= m * n; j++)
	//			cout << a[k][i][j] << " ";
	//		cout << "\n";
	//	}
	//	cout << "-----------------\n";
	//}
	

	int ans = 0;
	for (int i = 1; i <= m * n; i++)
		ans = max(ans, f[i]);

	cout << ans << endl;

	return 0;
}