题目大意：给定一个m*n的地图，一些点有障碍物，钢琴初始在一个点，每一个时间段能够选择向给定的方向移动一段距离，求最长路径长

朴素DP的话，我们有T个时间段，每一个时间段有m*n个点，n个时间，一定会超时

考虑到一个时间段全部的更新操作都是同样的，我们能够考虑单调队列优化

设队尾为(x,y),新插入的点为(x',y'),那么当Distance( (x,y) , (x',y') ) <= f[x'][y'] - f[x][y]时,(x,y)可被删掉

四遍单调队列就可以 O(T*m*n)

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 210

using namespace std;

typedef pair<int,int> abcd;

int n,m,k,ans;

char map[M][M];

int f[M][M],g[M][M];

abcd q[M];int r,h;

inline int Distance(const abcd &x,const abcd &y)

{

	return abs(x.first-y.first)+abs(x.second-y.second);

}

inline void Insert(const abcd &x)

{

	while( r!=h && Distance(x,q[r]) <= f[x.first][x.second] - f[q[r].first][q[r].second] )

		--r;

	q[++r]=x;

}

inline int Get_Ans(const abcd &x,int len)

{

	while( r!=h && Distance(q[h+1],x)>len )

		++h;

	if(r==h)

		return 0xefefefef;

	return f[q[h+1].first][q[h+1].second]+Distance(q[h+1],x);

}

void U(int len)

{

	int i,j;

	for(j=1;j<=n;j++)

	{

		r=h=0;

		for(i=m;i;i--)

			if(map[i][j]=='.')

			{

				abcd p(i,j);

				g[i][j]=max( f[i][j] , Get_Ans(p,len) );

				Insert(p);

			}

			else

				r=h=0;

	}

	memcpy(f,g,sizeof f);

}

void D(int len)

{

	int i,j;

	for(j=1;j<=n;j++)

	{

		r=h=0;

		for(i=1;i<=m;i++)

			if(map[i][j]=='.')

			{

				abcd p(i,j);

				g[i][j]=max( f[i][j] , Get_Ans(p,len) );

				Insert(p);

			}

			else

				r=h=0;

	}

	memcpy(f,g,sizeof f);

}

void L(int len)

{

	int i,j;

	for(i=1;i<=m;i++)

	{

		r=h=0;

		for(j=n;j;j--)

			if(map[i][j]=='.')

			{

				abcd p(i,j);

				g[i][j]=max( f[i][j] , Get_Ans(p,len) );

				Insert(p);

			}

			else

				r=h=0;

	}

	memcpy(f,g,sizeof f);

}

void R(int len)

{

	int i,j;

	for(i=1;i<=m;i++)

	{

		r=h=0;

		for(j=1;j<=n;j++)

			if(map[i][j]=='.')

			{

				abcd p(i,j);

				g[i][j]=max( f[i][j] , Get_Ans(p,len) );

				Insert(p);

			}

			else

				r=h=0;

	}

	memcpy(f,g,sizeof f);

}

int main()

{

	int i,j,x,y,z;

	cin>>m>>n>>x>>y>>k;

	for(i=1;i<=m;i++)

		scanf("%s",map[i]+1);

	memset(f,0xef,sizeof f);

	memset(g,0xef,sizeof g);

	f[x][y]=0;

	for(i=1;i<=k;i++)

	{

		scanf("%d%d%d",&x,&y,&z);

		switch(z)

		{

			case 1:U(y-x+1);break;

			case 2:D(y-x+1);break;

			case 3:L(y-x+1);break;

			case 4:R(y-x+1);break;

		}

	}

	for(i=1;i<=m;i++)

		for(j=1;j<=n;j++)

			ans=max(ans,f[i][j]);

	cout<<ans<<endl;

}