测试地址：瑰丽华尔兹
做法：设f(i,x,y)为第i段时间之后钢琴正好滑动到第x行第y列的最长滑动距离，很容易想到状态转移方程，按照倾斜方向分为四种情况考虑，这里只列出倾斜方向为1（向上）的情况：f(i,x,y)=max(f(i-1,x+s,y)+s)，其中s≤钢琴与当前倾斜方向的反方向上最近的障碍物或者船的边缘的距离（看上去很绕对不对...其实s就相当于钢琴在这一个时间段内滑动的距离），如果死算时间复杂度将是O(n^3*k)，难以接受，考虑单调队列优化。
还是讨论倾斜方向为1的情况。先将状态转移方程变形为f(i,x,y)=max(f(i-1,x+s,y)+(x+s))-x，令k=x+s，则f(i,x,y)=max(f(i-1,k,y)+k)-x，注意到k的取值范围是单调递增的，且f(i-1,k,y)+k为由k可在O(1)时间内确定的常数，满足单调队列优化的性质，因此可以将时间复杂度降低一维，变成O(n^2*k)，这样就可以接受了。对于其他倾斜方向，用类似的方法进行分析就可以了。
以下是本人代码：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define inf 999999999
using namespace std;
int n,m,x,y,t,f[2][210][210],que[210];
char g[210][210];
int main()
{
scanf("%d%d%d%d%d",&n,&m,&x,&y,&t);
for(int i=1;i<=n;i++)
{
getchar();
for(int j=1;j<=m;j++)
scanf("%c",&g[i][j]);
}
int now=0,past=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if (i==x&&j==y) f[past][i][j]=0;
else f[past][i][j]=-inf;
for(int i=1,a,b,c;i<=t;i++)
{
scanf("%d%d%d",&a,&b,&c);
int ti=b-a+1,h,t;
switch(c)
{
case 1:{
for(int j=1;j<=m;j++)
{
h=1,t=0;
for(int k=n;k>=1;k--)
{
if (g[k][j]=='x') h=t+2;
else
{
while(h<=t&&que[h]>k+ti) h++;
while(h<=t&&f[past][k][j]+k>f[past][que[t]][j]+que[t]) t--;
}
que[++t]=k;
if (h<=t) f[now][k][j]=f[past][que[h]][j]+que[h]-k;
else f[now][k][j]=-inf;
}
}
break;
}
case 2:{
for(int j=1;j<=m;j++)
{
h=1,t=0;
for(int k=1;k<=n;k++)
{
if (g[k][j]=='x') h=t+2;
else
{
while(h<=t&&que[h]<k-ti) h++;
while(h<=t&&f[past][k][j]-k>f[past][que[t]][j]-que[t]) t--;
}
que[++t]=k;
if (h<=t) f[now][k][j]=f[past][que[h]][j]-que[h]+k;
else f[now][k][j]=-inf;
}
}
break;
}
case 3:{
for(int j=1;j<=n;j++)
{
h=1,t=0;
for(int k=m;k>=1;k--)
{
if (g[j][k]=='x') h=t+2;
else
{
while(h<=t&&que[h]>k+ti) h++;
while(h<=t&&f[past][j][k]+k>f[past][j][que[t]]+que[t]) t--;
}
que[++t]=k;
if (h<=t) f[now][j][k]=f[past][j][que[h]]+que[h]-k;
else f[now][j][k]=-inf;
}
}
break;
}
case 4:{
for(int j=1;j<=n;j++)
{
h=1,t=0;
for(int k=1;k<=m;k++)
{
if (g[j][k]=='x') h=t+2;
else
{
while(h<=t&&que[h]<k-ti) h++;
while(h<=t&&f[past][j][k]-k>f[past][j][que[t]]-que[t]) t--;
}
que[++t]=k;
if (h<=t) f[now][j][k]=f[past][j][que[h]]-que[h]+k;
else f[now][j][k]=-inf;
}
}
break;
}
}
swap(now,past);
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=max(ans,f[past][i][j]);
printf("%d",ans);
return 0;
}