记录编号	456594	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]瑰丽华尔兹	最终得分	100
用户昵称	xzz_666	是否通过	通过
代码语言	C++	运行时间	1.143 s
提交时间	2017-10-05 09:10:26	内存使用	0.64 MiB

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstring>
#define Fname "adv1900"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
typedef long long ll;
il int gi(){
    rg int x=0;rg char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
const int maxx=201;
const int X[]={23333,-1,1,0,0},Y[]={23333,0,0,-1,1};
int n,m,_x,_y,k,inf;
int f[2][maxx][maxx];
int s[maxx],t[maxx],p[maxx];
char c[maxx][maxx];
il vd Max(int&a,int b){a=max(a,b);}
//f[i][j][k] i时间后到了(j,k) 求表示钢琴滑行的最长距离
int main(){
    freopen(Fname".in","r",stdin);
    freopen(Fname".out","w",stdout);
    n=gi(),m=gi(),_x=gi(),_y=gi(),k=gi();
    rep(i,1,n)scanf("%s",c[i]+1);
    rep(i,1,k)s[i]=gi(),t[i]=gi(),p[i]=gi();
    memset(f[0],-127,sizeof f[0]);inf=-f[0][0][0];
    f[0][_x][_y]=0;
    int now=0;
    rep(i,1,k){
        now^=1;
        memset(f[now],-127,sizeof f[now]);
        if(p[i]==1)rep(l,1,m){
				int lst=-1;
				drep(j,n,1){
					if(c[j][l]=='x')continue;
					static int lim,x,y;
					lim=min(t[i]-s[i]+1,lst+1),x=j,y=l;
					rep(o,0,lim){
						if(x==0||x==n+1||y==0||y==m+1)break;
						if(c[x][y]=='x')break;
						if(f[now][j][l]<o+f[now^1][x][y])lst=o,f[now][j][l]=o+f[now^1][x][y];
						x-=X[p[i]],y-=Y[p[i]];
					}
				}
			}
		else if(p[i]==2)rep(l,1,m){
				int lst=-1;
				rep(j,1,n){
					if(c[j][l]=='x')continue;
					static int lim,x,y;
					lim=min(t[i]-s[i]+1,lst+1),x=j,y=l;
					rep(o,0,lim){
						if(x==0||x==n+1||y==0||y==m+1)break;
						if(c[x][y]=='x')break;
						if(f[now][j][l]<o+f[now^1][x][y])lst=o,f[now][j][l]=o+f[now^1][x][y];
						x-=X[p[i]],y-=Y[p[i]];
					}
				}
			}
		else if(p[i]==3)rep(j,1,n){
				int lst=-1;
				drep(l,m,1){
					if(c[j][l]=='x')continue;
					static int lim,x,y;
					lim=min(t[i]-s[i]+1,lst+1),x=j,y=l;
					rep(o,0,lim){
						if(x==0||x==n+1||y==0||y==m+1)break;
						if(c[x][y]=='x')break;
						if(f[now][j][l]<o+f[now^1][x][y])lst=o,f[now][j][l]=o+f[now^1][x][y];
						x-=X[p[i]],y-=Y[p[i]];
					}
				}
			}
		else rep(j,1,n){
				int lst=-1;
				rep(l,1,m){
					if(c[j][l]=='x')continue;
					static int lim,x,y;
					lim=min(t[i]-s[i]+1,lst+1),x=j,y=l;
					rep(o,0,lim){
						if(x==0||x==n+1||y==0||y==m+1)break;
						if(c[x][y]=='x')break;
						if(f[now][j][l]<o+f[now^1][x][y])lst=o,f[now][j][l]=o+f[now^1][x][y];
						x-=X[p[i]],y-=Y[p[i]];
					}
				}
			}
    }
    int ans=-inf;
    rep(i,1,n)rep(j,1,m)Max(ans,f[now][i][j]);
    printf("%d\n",ans);
    return 0;
}