dp.
首先我们可以看到每个时间段只能往一个方向转移最多t步（t为时间段的长度），所以我们可以按时间段dp。因为这个前后值互不影响，也不用占用这一维空间就可以省去。
然后每个时间段内是一列一列（行） 进行递推。 如果朴素枚举是O(n^2)时间无法承受。所以每列（行）用一个单调队列维护dp，队首放着移动距离最大可以到达的点，这样复杂度就降到了O(n)。每次要递推n列（行）。所以总复杂度为O(k*n^2)。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ans first
#define pos second
const int maxn = 200 + 10;
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
pair<int,int> q[maxn],tmp;
int f[maxn][maxn];
char g[maxn][maxn];
int n,m,k,x,y,l,r,res; inline bool inrange(int x,int y) {
return x>=1 && x<=n && y>=1 && y<=m;
} void solve(int x,int y,int d,int len) {
l=r=0;
for(int i=0;inrange(x,y);i++,x+=dx[d],y+=dy[d]) {
if(g[x][y]=='x') l=r=0;
else {
tmp.ans=f[x][y]; tmp.pos=i;
while(l<r && q[r-1].ans+(i-q[r-1].pos)<=tmp.ans) r--;
q[r++]=tmp;
while(l<r && (i-q[l].pos)>len) l++;
f[x][y]=q[l].ans+(i-q[l].pos);
res=max(res,f[x][y]);
}
}
} int main() {
scanf("%d%d%d%d%d",&n,&m,&x,&y,&k);
for(int i=1;i<=n;i++) scanf("%s",g[i]+1); memset(f,0x80,sizeof(f)); f[x][y]=0;
for(int i=1,s,e,d,len;i<=k;i++) {
scanf("%d%d%d",&s,&e,&d),len=e-s+1;
if(d==1) for(int j=1;j<=m;j++) solve(n,j,0,len);
else if(d==2) for(int j=1;j<=m;j++) solve(1,j,1,len);
else if(d==3) for(int j=1;j<=n;j++) solve(j,m,2,len);
else for(int j=1;j<=n;j++) solve(j,1,3,len);
}
printf("%d\n",res);
return 0;
}