题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1499

题目分类：动态规划，单调队列优化

题意：

给出一个有障碍的网格图和一个可移动的棋子，每个时间段中移动的方向是确定的，可以控制他的停止，问最多可以走多少格。

题解：

使用动态规划dp[i][j][k]表示到了第i行第j列时间为k最多走几格，发现状态数过多。

将最后一位从时间改为时间段，这样需要额外的200转移时间。

可以发现转移满足单调队列优化规律。

程序：

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[210][210][210];
char str[210][210];
int n,m,k,tx,ty,x1,x2,x3;
int a[210],bar[210];/*
struct node
{
	int lef[12000],rig[12000],val[12000];
	inline void build(int x,int le,int ri)
	{
		lef[x]=le;
		rig[x]=ri;
		if(le==ri)
		{
			val[x]=a[le];
			return;
		}
		build(x*2,le,(le+ri)/2);
		build(x*2+1,(le+ri)/2+1,ri);
		val[x]=max(val[x*2],val[x*2+1]);
	}
	inline int query(int x,int le,int ri)
	{
		if(le>ri)return -1200000;
		if(le<=lef[x]&&ri>=rig[x])return val[x];
		int ss=-1200000;
		if(le<=rig[x*2])ss=max(ss,query(x*2,le,ri));
		if(ri>=lef[x*2+1])ss=max(ss,query(x*2+1,le,ri));
		return ss;
	}
}sgt;
inline void up(int x,int last)
{
	for (int j=1;j<=m;j++)
	{
		for (int i=1;i<=n;i++)
		{
			a[i]=dp[x-1][i][j]+i;
		}
		sgt.build(1,1,n);
		bar[n+1]=n+1;
		for (int i=n;i>=1;i--)
		{
			if(str[i][j]=='x')
			bar[i]=i;
			else
			bar[i]=bar[i+1];
		}
		for (int i=n;i>=1;i--)
		{
			int tp=bar[i];
			if(bar[i]-i>last+1)tp=i+last+1;
			dp[x][i][j]=sgt.query(1,i,tp-1)-i;
		}
	}
}
inline void down(int x,int last)
{
	for (int j=1;j<=m;j++)
	{
		for (int i=1;i<=n;i++)
		{
			a[i]=dp[x-1][i][j]-i;
		}
		sgt.build(1,1,n);
		bar[0]=0;
		for (int i=1;i<=n;i++)
		{
			if(str[i][j]=='x')
			bar[i]=i;
			else
			bar[i]=bar[i-1];
		}
		for (int i=1;i<=n;i++)
		{
			int tp=bar[i];
			if(i-bar[i]>last+1)tp=i-last-1;
			dp[x][i][j]=sgt.query(1,tp+1,i)+i;
		}
	}
}
inline void left(int x,int last)
{
	for (int j=1;j<=n;j++)
	{
		for (int i=1;i<=m;i++)
		{
			a[i]=dp[x-1][j][i]+i;
		}
		sgt.build(1,1,m);
		bar[m+1]=m+1;
		for (int i=m;i>=1;i--)
		{
			if(str[j][i]=='x')
			bar[i]=i;
			else
			bar[i]=bar[i+1];
		}
		for (int i=m;i>=1;i--)
		{
			int tp=bar[i];
			if(bar[i]-i>last+1)tp=i+last+1;
			dp[x][j][i]=sgt.query(1,i,tp-1)-i;
		}
	}
}
inline void right(int x,int last)
{
	for (int j=1;j<=n;j++)
	{
		for (int i=1;i<=m;i++)
		{
			a[i]=dp[x-1][j][i]-i;
		//	printf("a:::%d %d %d\n",j,i,a[i]);
		}
		sgt.build(1,1,m);
		bar[0]=0;
		for (int i=1;i<=m;i++)
		{
			if(str[j][i]=='x')
			bar[i]=i;
			else
			bar[i]=bar[i-1];
		//	printf("%d %d %d\n",j,i,bar[i]);
		}
		for (int i=1;i<=m;i++)
		{
			int tp=bar[i];
			if(i-bar[i]>last+1)tp=i-last-1;
		//	printf("%d %d %d\n",j,i,tp);
			dp[x][j][i]=sgt.query(1,tp+1,i)+i;
		}
	}
}*/
int l,r,q[12000];
inline void up(int x,int last)
{
	for (int j=1;j<=m;j++)
	{
		l=0;r=-1;
		for (int i=n;i>=1;i--)
		{
			if(str[i][j]=='x'){l=0;r=-1;}
			else
			{
				while (l<=r&&dp[x-1][q[r]][j]+q[r]<=dp[x-1][i][j]+i)r--;
				r++;
				q[r]=i;
				while (q[l]-i>last)l++;
				dp[x][i][j]=dp[x-1][q[l]][j]+q[l]-i;
			}
		}
	}
}
inline void down(int x,int last)
{
	for (int j=1;j<=m;j++)
	{
		l=0;r=-1;
		for (int i=1;i<=n;i++)
		{
			if(str[i][j]=='x'){l=0;r=-1;}
			else
			{
				while (l<=r&&dp[x-1][q[r]][j]-q[r]<=dp[x-1][i][j]-i)r--;
				r++;
				q[r]=i;
				while (i-q[l]>last)l++;
				dp[x][i][j]=dp[x-1][q[l]][j]-q[l]+i;
			}
		}
	}
}
inline void left(int x,int last)
{
	for (int j=1;j<=n;j++)
	{
		l=0;r=-1;
		for (int i=m;i>=1;i--)
		{
			if(str[j][i]=='x'){l=0;r=-1;}
			else
			{
				while (l<=r&&dp[x-1][j][q[r]]+q[r]<=dp[x-1][j][i]+i)r--;
				r++;
				q[r]=i;
				while (q[l]-i>last)l++;
				dp[x][j][i]=dp[x-1][j][q[l]]+q[l]-i;
			}
		}
	}
}
inline void right(int x,int last)
{
	for (int j=1;j<=n;j++)
	{
		l=0;r=-1;
		for (int i=1;i<=m;i++)
		{
			if(str[j][i]=='x'){l=0;r=-1;}
			else
			{
				while (l<=r&&dp[x-1][j][q[r]]-q[r]<=dp[x-1][j][i]-i)r--;
				r++;
				q[r]=i;
				while (i-q[l]>last)l++;
				dp[x][j][i]=dp[x-1][j][q[l]]-q[l]+i;
			}
		}
	}
}
int main()
{
	scanf("%d %d %d %d %d",&n,&m,&tx,&ty,&k);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",str[i]+1);
	}
	for (int i=0;i<=k;i++)
	{
		for (int j=1;j<=n;j++)
		{
			for (int l=1;l<=m;l++)
			{
				dp[i][j][l]=-1200000;
			}
		}
	}
	dp[0][tx][ty]=0;
	for (int i=1;i<=k;i++)
	{
		scanf("%d %d %d",&x1,&x2,&x3);
		if(x3==1)up(i,x2-x1+1);
		if(x3==2)down(i,x2-x1+1);
		if(x3==3)left(i,x2-x1+1);
		if(x3==4)right(i,x2-x1+1);
	}
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			ans=max(ans,dp[k][i][j]);
		}
	}printf("%d\n",ans);
	return 0;
}