记录编号	188062	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]瑰丽华尔兹	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.557 s
提交时间	2015-09-21 20:02:04	内存使用	0.52 MiB

#include<cstdio>
#include<iostream>
#include<deque>
using namespace std;
const int SIZEN=210,INF=0x7fffffff/2;
int N,M,x,y,K,d[SIZEN],tim[SIZEN];
bool mp[SIZEN][SIZEN]={0};
int f[SIZEN][SIZEN]={0},ans=0;
//1代表上，2代表下，3代表左，4代表右
void read()
{
	scanf("%d%d%d%d%d",&N,&M,&x,&y,&K);
	char str[SIZEN];
	for(int i=1;i<=N;i++)
	{
		scanf("%s",str);
		for(int j=0;j<M;j++)
			if(str[j]=='x') mp[i][j+1]=1;
	}
	int s,t;
	for(int i=1;i<=K;i++)
	{
		scanf("%d%d%d",&s,&t,&d[i]);
		tim[i]=t-s+1;
	}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			f[i][j]=-INF;
	f[x][y]=0;
}
void up(int x)//从下到上
{
	deque<int> Q;deque<int> D;
	for(int i=1;i<=M;i++)
	{
		Q.clear();D.clear();
		for(int j=N;j>=1;j--)
		{
			if(mp[j][i]){Q.clear();D.clear();continue;}
			while(!D.empty()&&D.front()-j>tim[x]) {Q.pop_front();D.pop_front();}
			while(!Q.empty()&&Q.back()<f[j][i]+j&&f[j][i]>=0) {Q.pop_back();D.pop_back();}
			Q.push_back(f[j][i]+j);D.push_back(j);
			//cout<<j<<" "<<i<<" "<<f[j][i]+j<<endl;
			f[j][i]=Q.front()-j;
		}
	}
}
void down(int x)
{
	deque<int> Q;deque<int> D;
	for(int i=1;i<=M;i++)
	{
		Q.clear();D.clear();
		for(int j=1;j<=N;j++)
		{
			if(mp[j][i]){Q.clear();D.clear();continue;}
			while(!D.empty()&&j-D.front()>tim[x]) {Q.pop_front();D.pop_front();}
			while(!Q.empty()&&Q.back()<f[j][i]-j&&f[j][i]>=0) {Q.pop_back();D.pop_back();}
			Q.push_back(f[j][i]-j);D.push_back(j);
			//cout<<j<<" "<<i<<" "<<f[j][i]-j<<endl;
			f[j][i]=Q.front()+j;
		}
	}
}
void left(int x)
{
	deque<int> Q;
	deque<int> D;
	for(int i=1;i<=N;i++)
	{
		Q.clear();
		D.clear();
		for(int j=M;j>=1;j--)
		{
			if(mp[i][j]){Q.clear();D.clear();continue;}
			while(!D.empty()&&D.front()-j>tim[x]) {Q.pop_front();D.pop_front();}
			while(!Q.empty()&&Q.back()<f[i][j]+j&&f[i][j]>=0) {Q.pop_back();D.pop_back();}
			Q.push_back(f[i][j]+j);
			D.push_back(j); 
			//cout<<j<<" "<<i<<" "<<f[j][i]+j<<endl;
			f[i][j]=Q.front()-j;
		}
	}
}
void right(int x)
{
	deque<int> Q;deque<int> D;
	for(int i=1;i<=N;i++)
	{
		Q.clear();D.clear();
		for(int j=1;j<=M;j++)
		{
			if(mp[i][j]){Q.clear();D.clear();continue;}
			while(!D.empty()&&j-D.front()>tim[x]) {Q.pop_front();D.pop_front();}
			while(!Q.empty()&&Q.back()<f[i][j]-j&&f[i][j]>=0) {Q.pop_back();D.pop_back();}
			Q.push_back(f[i][j]-j);D.push_back(j);
			//cout<<i<<" "<<j<<" "<<Q.size()<<endl;
			//cout<<i<<" "<<j<<" "<<f[i][j]<<" "<<Q.front()<<" "<<Q.size()<<endl;
			f[i][j]=Q.front()+j;
		}
	}
}
void work()
{
	for(int k=1;k<=K;k++)
	{
		if(d[k]==1) up(k);
		if(d[k]==2) down(k);
		if(d[k]==3) left(k);
		if(d[k]==4) right(k);
		/*cout<<tim[k]<<" "<<d[k]<<endl;
		for(int i=1;i<=N;i++)
	    {
		for(int j=1;j<=M;j++)
			cout<<f[i][j]<<" ";
		cout<<endl;
	    }
		cout<<endl;*/
	}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			ans=max(ans,f[i][j]);
	printf("%d",ans);
}
int main()
{
	freopen("adv1900.in","r",stdin);
	freopen("adv1900.out","w",stdout);
	read();
	work();
	return 0;
}