Description：

一个 $N\times M$ 的矩阵，某些方格不能到达，有 $K$ 个时间段 $t$ ，每个时间段内一个最开始在 $(x,y)$ 的物品会向上下左右某个方向移动一格，可以用魔法使得物品在某一个时刻停止，求最长滑动距离。

$1\le N,M,K\le 200,1\le \sum t\le 40000$

Solution：

可以发现对于每个状态在当前时刻能转移过来的是一个滑动窗口，长度为 $t$ ，于是用单调队列优化 $DP$ 即可，对于不能到达的点的情况直接把队列清空即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline char getc()

{

	register char c = getchar();

	while(c != '.' && c != 'x')c = getchar();

	return c;

}

int n,m,x,y,k;

#define MAXN 210

int f[MAXN][MAXN][MAXN];

char p[MAXN][MAXN];

int q[MAXN],head,tail;

int main()

{

	scanf("%d%d%d%d%d",&n,&m,&x,&y,&k);

	memset(f,0xc0,sizeof(f));

	f[0][x][y] = 0;

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			p[i][j] = getc();

	int l,r,dir;

	for(int w = 1;w <= k;++w)

	{

		scanf("%d%d%d",&l,&r,&dir);

		if(dir == 1)

		{

			for(int j = 1;j <= m;++j)

			{

				memset(q,0,sizeof(q));head = 1;tail = 0;

				for(int i = n;i >= 1;--i)

				{

					if(p[i][j] == 'x')head = tail + 1;

					while(head <= tail && q[head] - i > r - l + 1)++head;

					while(head <= tail && q[tail] - i + f[w - 1][q[tail]][j] < f[w - 1][i][j])--tail;

					q[++tail] = i;

					f[w][i][j] = f[w - 1][q[head]][j] + q[head] - i;

				}

			}

		}

		if(dir == 2)

		{

			for(int j = 1;j <= m;++j)

			{

				memset(q,0,sizeof(q));head = 1;tail = 0;

				for(int i = 1;i <= n;++i)

				{

					if(p[i][j] == 'x')head = tail + 1;

					while(head <= tail && i - q[head] > r - l + 1)++head;

					while(head <= tail && i - q[tail] + f[w - 1][q[tail]][j] < f[w - 1][i][j])--tail;

					q[++tail] = i;

					f[w][i][j] = f[w - 1][q[head]][j] + i - q[head];

				}

			}

		}

		if(dir == 3)

		{

			for(int i = 1;i <= n;++i)

			{

				memset(q,0,sizeof(q));head = 1;tail = 0;

				for(int j = m;j >= 1;--j)

				{

					if(p[i][j] == 'x')head = tail + 1;

					while(head <= tail && q[head] - j > r - l + 1)++head;

					while(head <= tail && q[tail] - j + f[w - 1][i][q[tail]] < f[w - 1][i][j])--tail;

					q[++tail] = j;

					f[w][i][j] = f[w - 1][i][q[head]] + q[head] - j;

				}

			}

		}

		if(dir == 4)

		{

			for(int i = 1;i <= n;++i)

			{

				memset(q,0,sizeof(q));head = 1;tail = 0;

				for(int j = 1;j <= m;++j)

				{

					if(p[i][j] == 'x')head = tail + 1;

					while(head <= tail && j - q[head] > r - l + 1)++head;

					while(head <= tail && j - q[tail] + f[w - 1][i][q[tail]] < f[w - 1][i][j])--tail;

					q[++tail] = j;

					f[w][i][j] = f[w - 1][i][q[head]] + j - q[head];

				}

			}

		}

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

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

		}

	}

	cout << ans << endl;

	return 0;

}