石头游戏题解

题目描述

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

操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。每秒钟,所有格子同时执行各自操作序列里的下一个字符。序列中的每个字符是以下格式之一:

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

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

输入

第一行4个整数n, m, t, act。
接下来n行,每行m个字符,表示每个格子对应的操作序列。
最后act行,每行一个字符串,表示从0开始的每个操作序列。

输出

一个整数:游戏进行了t秒之后,所有方格中最多的格子有多少个石头。

样例输入

1 6 10 3
011112
1E
E
0

样例输出

3

提示

【数据范围】

1≤m,n≤8,

1≤t≤10^8,

1≤act≤10

题解:

        请注意,这不是一道模拟,而是一道带模拟的矩阵加速递推。由于mn\leqslant64所以考虑把地图压成一维(方便之后的矩阵算法),同时,需要在第mn+1位定为1,表示取石子(毕竟全是0也无法转移得到非0的答案)。此时只用关注每一秒的转移矩阵了。如果是0~9的数字,那么直接在这一列的第mn+1行赋成该数字,同时在这个位置也要赋值为1,表示既取了这个数,又多取了相应的石子。如果是D,可以考虑不加操作,那么下一次这个位置就直接变成0了。如果是方向ESWN,那么就是考虑这个位置不取,同时在相应的位置取这个位置的值(1)。

        以上叙述比较抽象,现在来举几个例子。举例子之前,先讲讲我的压位方式:(x-1)*m+y。就是点(x,y)的平面表示,可以证明这是唯一确定并且豪不浪费空间的压法。

        假设枚举到点(x,y),那么此处的平面表示为k=(x-1)\times m+1,那么转移矩阵中的(k,k)应该赋值为1,表示取本身。同时如果这个位置的操作是放i个石子,那么在(mn+1,k)的位置应该赋值为i,表示要多取i个石子。注意,每个纵坐标(除了mn+1)的一列都表示该位置所需要的转移方式。如果要拿走这一格所有石子(D),那么就让第k列的每一个元素都为0,无论原状态是什么,这样转移之后一定为0。如果是方向,这里要声明:根据样例,如果超界就超界,还是要进行转移操作,只不过效果和D差不多了。同样的,以E方向举例,如果要转移,首先得保证x

        我的转移矩阵change[z],z\ni [1,60]表示从第1秒开始连续进行操作至第n秒的所有转移矩阵的乘积。相当于我要求第3秒的矩阵,直接用初始矩阵乘以change[3]就行了。至于初始矩阵,平面位置全都是0,第mn+1位是1。UP数组表示中转站。可以很容易处理出change[60]。由于所求的t很大,所以可以用矩阵加速递推快速搞定60的倍数。剩下的余数如果为k,直接乘以change[k]即可。为什么是60?因为每一次操作不超过6,而1,2,3,4,5,6的最小公倍数就是60。因此操作时要循环,每隔60次的转移矩阵一定是循环的。

        把所有的转移矩阵乘起来,最后乘上初始矩阵,然后枚举每一个位置的石子数,求出最大值即可。注意要开long long(数组不要开小,否则会出奇怪的问题,还不会报错)。

参考代码:

#include
#include
#define LL long long
using namespace std;
LL n,m,t,act,e_map[12][12],way[20][80],len,maxn=0;
char s[12],p[12];
LL change[70][70][70],UP[70][70],ret[70][70];
void qpow(LL k)
{
	while(k)
	{
		if(k&1ll)
		{
			for(int i=1;i<=m*n+1;i++)
			  for(int j=1;j<=m*n+1;j++)
			    for(int k=1;k<=m*n+1;k++)
			      UP[i][j]+=ret[i][k]*change[k][j][60ll];
			for(int i=1;i<=m*n+1;i++)
			  for(int j=1;j<=m*n+1;j++)
			    {
			    	ret[i][j]=UP[i][j];
			    	UP[i][j]=0;
				}
		}
		for(int i=1;i<=m*n+1;i++)
		  for(int j=1;j<=m*n+1;j++)
		    for(int k=1;k<=m*n+1;k++)
		      UP[i][j]+=change[i][k][60ll]*change[k][j][60ll];
		for(int i=1;i<=m*n+1;i++)
		  for(int j=1;j<=m*n+1;j++)
		    {
		    	change[i][j][60ll]=UP[i][j];
		    	UP[i][j]=0;
			}
		k/=2ll;
	}
}
int main()
{
	scanf("%lld%lld%lld%lld",&n,&m,&t,&act);
	for(int i=1ll;i<=n;i++)
	{
		scanf("%s",s);
		for(int j=1;j<=m;j++)
		e_map[i][j]=s[j-1ll]-'0'+1ll;
	}
	for(int i=1ll;i<=act;i++)
	{
		scanf("%s",s);
		len=strlen(s);
		for(int j=1ll;j<=60ll;j++)
		{
			if(s[(j-1ll)%len]>='0'&&s[(j-1ll)%len]<='9')
			way[i][j]=s[(j-1)%len]-'0';
			else if(s[(j-1ll)%len]=='E')
			way[i][j]=11ll;
			else if(s[(j-1)%len]=='S')
			way[i][j]=12ll;
			else if(s[(j-1)%len]=='W')
			way[i][j]=13ll;
			else if(s[(j-1)%len]=='N')
			way[i][j]=14ll;
			else way[i][j]=15ll;
		}
	}
	for(int i=1ll;i<=m*n+1ll;i++)
	change[i][i][0]=ret[i][i]=1ll;
	for(int i=1ll;i<=60ll;i++)
	{
		for(int x=1ll;x<=n;x++)
		  for(int y=1ll;y<=m;y++)
		    {
		    	LL ilt=way[e_map[x][y]][i];
		    	if(ilt<10ll)
		    	{
		    		UP[(x-1ll)*m+y][(x-1ll)*m+y]=1ll;
		    		UP[m*n+1ll][(x-1ll)*m+y]=ilt;
				}
				else if(ilt==11ll&&y1)
				UP[(x-1ll)*m+y][(x-1ll)*m+y-1ll]=1ll;
				else if(ilt==14&&x>1)
				UP[(x-1ll)*m+y][(x-2ll)*m+y]=1ll;
			}
		UP[m*n+1ll][m*n+1ll]=1ll;
		for(int x=1ll;x<=m*n+1ll;x++)
		{
			for(int y=1ll;y<=m*n+1ll;y++)
			{
				for(int k=1ll;k<=m*n+1ll;k++)
				{
					change[x][y][i]+=change[x][k][i-1ll]*UP[k][y];
				}
			}
		}
		for(int x=1ll;x<=n*m+1ll;x++)
		  for(int y=1ll;y<=n*m+1ll;y++)
		    UP[x][y]=0;
	}
	qpow(t/60ll);
	for(int i=1ll;i<=m*n+1ll;i++)
	  for(int j=1ll;j<=m*n+1ll;j++)
	    for(int k=1ll;k<=n*m+1ll;k++)
	      UP[i][j]+=ret[i][k]*change[k][j][t%60ll];
	for(int i=1ll;i<=m*n;i++)
	if(UP[m*n+1ll][i]>maxn) maxn=UP[m*n+1ll][i];
	printf("%lld",maxn);
	return 0;
}

        

你可能感兴趣的