石头游戏
权限题.
描述
石头游戏在一个 n 行 m 列 (1≤n,m≤8) 的网格上进行, 每个格子对应一种操作序列, 操作序列至多有 10 种, 分别用 0~9 这 10 个数字指明.
操作序列是一个长度不超过 6 且循环执行, 每秒执行一个字符的字符串. 每秒钟, 所有格子同时执行各自操作序列里的下一个字符. 序列中的每个字符是以下格式之一:
数字 0~9: 表示拿 0~9 个石头到该格子.
NWSE: 表示把这个格子内所有的石头推到相邻的格子, N 表示上方, W 表示左方, S 表示下方, E 表示右方.
D: 表示拿走这个格子的所有石头.
给定每种操作序列对应的字符串, 以及网格中每个格子对应的操作序列, 求石头游戏进行了 t 秒之后, 石头最多的格子里有多少个石头. 在游戏开始时, 网格是空的.
- SimpleInput:
- 1 6 10 3
- 011112
- 1E
- E
- 0
- SimpleOutput
- 3
- Solution:
首先 不妨把 n*m 的网格压成一行, 方便接下来的转移, 并设 id(i,j) 为 i,j 在序列中的位置.
其次 由于操作序列长度不超过 6, 那么由于 lcm(1,2,3,4,5,6)=60, 所以每 60 次操作后, 操作序列的状态又会回到初始态.
那么 这启示着: 如果想把操作序列状态存下来只需要记录 60 种即可.
所以 考虑把每一种状态存入矩阵.
然后对应的进行一下转移, 用矩阵快速幂加速即可.
关于矩阵的构造, 有一个很巧妙的是: 增加一个第 0 行 / 列.
在状态矩阵中, 第 0 行代表的 石头来源 且此行的值始终为 1.
在转移矩阵中, A[0,id(i,j)] 则代表着 i,j 这个位置从 石头来源 获取了石头, 特别的, A[0,0] 应恒为 1.
转移矩阵的构造想清楚了就没很大问题了.
- Code:
- #include
- #include
- #include
- #include
- #include
- #define RG register
- #define IL inline
- #define int long long
- #define DB double
- using namespace std;
- IL int gi() {
- RG int x=0,w=0; char ch=getchar();
- while(ch<'0'||ch>'9') {if(ch=='-') w=1;ch=getchar();}
- while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
- return w?-x:x;
- }
- const int N=10;
- char op[N],s[N][N];
- int n,m,t,cnt,Max,a[N][N],id[N][N];
- struct Matrix{
- int MT[N*N][N*N];
- Matrix operator *(const Matrix &b) {
- RG int i,j,k,M=n*m;
- RG Matrix c;
- for(i=0;i<=M;++i)
- for(j=0;j<=M;++j) c.MT[i][j]=0;
- for(i=0;i<=M;++i)
- for(k=0;k<=M;++k)
- for(j=0;j<=M;++j)
- c.MT[i][j]+=MT[i][k]*b.MT[k][j];
- return c;
- }
- }f,A[62],PA[62];
- IL Matrix qpow(Matrix x,int p) {
- RG int i,j;
- RG Matrix ans;
- for(i=0;i<=n*m;++i)
- for(j=0;j<=n*m;++j)
- if(i==j) ans.MT[i][j]=1;
- else ans.MT[i][j]=0;
- for(;p;p>>=1,x=x*x)
- if(p&1) ans=ans*x;
- return ans;
- }
- signed main()
- {
- RG char ss;
- RG int i,j,k,p,q,T;
- n=gi(),m=gi(),t=gi(),cnt=gi();
- for(i=1;i<=n;++i) {
- scanf("%s",op);
- for(j=1;j<=m;++j)
- a[i][j]=(op[j-1]^48),id[i][j]=(i-1)*m+j;
- }
- for(i=0;i<cnt;++i) scanf("%s",s[i]);
- f.MT[0][0]=1;
- for(k=1;k<=60;++k) {
- A[k].MT[0][0]=1;
- for(i=1;i<=n;++i) {
- for(j=1;j<=m;++j) {
- T=(k-1)%strlen(s[a[i][j]]);
- ss=s[a[i][j]][T];
- if(ss>='0'&&ss<='9')
- A[k].MT[0][id[i][j]]=ss^48,A[k].MT[id[i][j]][id[i][j]]=1;
- if(ss=='N'&&i>1) A[k].MT[id[i][j]][id[i-1][j]]=1;
- if(ss=='S'&&i<n) A[k].MT[id[i][j]][id[i+1][j]]=1;
- if(ss=='W'&&j>1) A[k].MT[id[i][j]][id[i][j-1]]=1;
- if(ss=='E'&&j<m) A[k].MT[id[i][j]][id[i][j+1]]=1;
- }
- }
- }
- q=t%60,p=(t-q)/60;
- for(i=2,PA[1]=A[1];i<=60;++i) PA[i]=PA[i-1]*A[i];
- f=f*qpow(PA[60],p)*PA[q];
- for(i=1;i<=n*m;++i) Max=max(Max,f.MT[0][i]);
- printf("%lld\n",Max);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3010912.html