https://class.51nod.com/Html/Textbook/Problem.html#problemId=3983&textbookChapterId=724
https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337
移动与时间段有关，如果按照时间段划分状态那么每一段内只有一条线性的转移。
需要一行一行或一列一列转移，故要存位置。
接下来只需写一个函数用来用单调队列求最值，可以把点对替换掉传统的下标，传入偏移量，这样四个方向的转移只需要一个函数。
复杂度 \(o(NMK)\)。
#include<iostream>
#include<cstring>
#include<cmath>
#include<utility>
using namespace std;
const int N=210,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int I,n,m,now,lst,x,y,k,f[2][N][N],len;
char s[N][N];
struct node{
int x,y;
}q[N];
#define dis(a,b,c,d) (abs(d-b)+abs(c-a))
#define cdis dis(q[hh].x,q[hh].y,x,y)
void put(int b,int c,int fa,int fb){
printf("from (%d,%d,%d)=%d\n",I-1,fa,fb,f[I-1&1][fa][fb]);
printf("f[%d][%d][%d]=%d\n",I,b,c,f[I&1][b][c]);
}
void calc(int x,int y,int dx,int dy){
int hh=0,tt=-1;
for(;x>0&&y>0&&x<=n&&y<=m;x+=dx,y+=dy){
if(s[x][y]=='x')hh=0,tt=-1;
else{
while(hh<=tt&&cdis>len)++hh;
while(hh<=tt&&f[lst][q[tt].x][q[tt].y]+dis(q[tt].x,q[tt].y,x,y)
<=f[lst][x][y])--tt;
q[++tt]={x,y};
if(hh<=tt)
f[now][x][y]=f[lst][q[hh].x][q[hh].y]+cdis;//,put(x,y,q[hh].x,q[hh].y);
}
}
}
int main(){
#ifdef LOCAL
freopen("1.txt","r",stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
cin>>n>>m>>x>>y>>k;
for(int i=1;i<=n;++i)cin>>(s[i]+1);
for(int i=1;i<=n;++i)memset(f[0][i]+1,128,m*4);
f[0][x][y]=0;
for(I=1;I<=k;++I){
now=I&1,lst=!now;
for(int i=1;i<=n;++i)
memset(f[now][i]+1,128,m*4);
int s,t,d;
cin>>s>>t>>d;
len=t-s+1;
int dx=::dx[d-1],dy=::dy[d-1];
if(d==1)
for(int i=1;i<=m;++i)
calc(n,i,dx,dy);
else if(d==2)
for(int i=1;i<=m;++i)
calc(1,i,dx,dy);
else if(d==3)
for(int i=1;i<=n;++i)
calc(i,m,dx,dy);
else
for(int i=1;i<=n;++i)
calc(i,1,dx,dy);
}
int ans=0;
for(int x=1;x<=n;++x)
for(int y=1;y<=m;++y)
ans=max(ans,f[k&1][x][y]);
cout<<ans;
return 0;
}