记录编号	62386	评测结果	AAAAAAAAAA
题目名称	340.[NOI 2005]瑰丽华尔兹	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.628 s
提交时间	2013-06-25 18:51:38	内存使用	0.53 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<stack>
#include<vector>
#include<fstream>
using namespace std;
const int SIZEN=210,SIZEK=210,INF=0x7fffffff;
int N,M,K;//N行M列
//这里的行列从1开始
int inx,iny;//初始位置
bool board[SIZEN][SIZEN]={0};//若为1表示有家具
int s[SIZEK]={0},t[SIZEK]={0},d[SIZEK]={0};//描述K个区间
//1上,2下,3左,4右
int f[SIZEN][SIZEN]={0};
void uprow(int k,int len){//对下一个时段第k列进行单调队列递推,方向是从下向上
	deque<int> Q;
	int f0[SIZEN]={0};
	int i,temp;
	for(i=1;i<=N;i++) f0[i]=f[i][k];
	for(i=N;i>=1;i--){
		if(board[i][k]){
			Q.clear();
			continue;
		}
		while(Q.size()&&f0[Q.back()]+Q.back()-i<=f0[i]) Q.pop_back();
		Q.push_back(i);
		temp=Q.front()-i;
		if(temp>len) Q.pop_front();
		f[i][k]=f0[Q.front()]+Q.front()-i;
	}
}
void up(int k){//第k个区间
	int i,temp=t[k]-s[k]+1;
	for(i=1;i<=M;i++) uprow(i,temp);
}
void downrow(int k,int len){//对下一个时段第k列进行单调队列递推,方向是从上向下
	deque<int> Q;
	int f0[SIZEN]={0};
	int i,temp;
	for(i=1;i<=N;i++) f0[i]=f[i][k];
	for(i=1;i<=N;i++){
		if(board[i][k]){
			Q.clear();
			continue;
		}
		while(Q.size()&&f0[Q.back()]+i-Q.back()<=f0[i]) Q.pop_back();
		Q.push_back(i);
		temp=i-Q.front();
		if(temp>len) Q.pop_front();
		f[i][k]=f0[Q.front()]+i-Q.front();		
	}
}
void down(int k){//第k个区间
	int i,temp=t[k]-s[k]+1;
	for(i=1;i<=M;i++) downrow(i,temp);
}
void leftline(int k,int len){//对下一个时段第k行进行单调队列递推,方向是从右向左
	deque<int> Q;
	int f0[SIZEN]={0};
	int i,temp;
	for(i=1;i<=M;i++) f0[i]=f[k][i];
	for(i=M;i>=1;i--){
		if(board[k][i]){
			Q.clear();
			continue;
		}
		while(Q.size()&&f0[Q.back()]+Q.back()-i<=f0[i]) Q.pop_back();
		Q.push_back(i);
		temp=Q.front()-i;
		if(temp>len) Q.pop_front();
		f[k][i]=f0[Q.front()]+Q.front()-i;
	}
}
void left(int k){//第k个区间
	int i,temp=t[k]-s[k]+1;
	for(i=1;i<=N;i++) leftline(i,temp);
}
void rightline(int k,int len){//对下一个时段第k行进行单调队列递推,方向是从左向右
	deque<int> Q;
	int f0[SIZEN]={0};
	int i,temp;
	for(i=1;i<=M;i++) f0[i]=f[k][i];
	for(i=1;i<=M;i++){
		if(board[k][i]){
			Q.clear();
			continue;
		}
		while(Q.size()&&f0[Q.back()]+i-Q.back()<=f0[i]) Q.pop_back();
		Q.push_back(i);
		temp=i-Q.front();
		if(temp>len) Q.pop_front();
		f[k][i]=f0[Q.front()]+i-Q.front();
	}
}
void right(int k){//第k个区间
	int i,temp=t[k]-s[k]+1;
	for(i=1;i<=N;i++) rightline(i,temp);
}
void dp(void){
	int i,j;
	for(i=1;i<=K;i++){
		switch(d[i]){
			case 1:up(i);break;
			case 2:down(i);break;
			case 3:left(i);break;
			case 4:right(i);break;
		}
	}
	int ans=-INF;
	for(i=1;i<=N;i++){
		for(j=1;j<=M;j++) ans=max(ans,f[i][j]);
	}
	printf("%d\n",ans);
}
void init(void){
	scanf("%d%d%d%d%d",&N,&M,&inx,&iny,&K);
	int i,j;
	char ch;
	for(i=1;i<=N;i++){
		getchar();
		for(j=1;j<=M;j++){
			cin>>ch;
			board[i][j]=(ch=='x');
		}
	}
	for(i=1;i<=K;i++) scanf("%d%d%d",&s[i],&t[i],&d[i]);
	for(i=1;i<=N;i++){
		for(j=1;j<=M;j++) f[i][j]=-INF;
	}
	f[inx][iny]=0;
}
int main(){
	freopen("adv1900.in","r",stdin);
	freopen("adv1900.out","w",stdout);
	init();
	dp();
	return 0;
}