【记忆化搜索】bzoj3208 花神的秒题计划Ⅰ

暴力

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 701

const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};

int n,mem[N][N],a[N][N],m;

bool cant[N][N];

int f(int x,int y)

{

	if(mem[x][y]) return mem[x][y];

	mem[x][y]=1;

	for(int i=0;i<4;++i)

	  if(x+dx[i]>0&&x+dx[i]<=n&&y+dy[i]>0&&y+dy[i]<=n&&(!cant[x+dx[i]][y+dy[i]])&&a[x][y]>a[x+dx[i]][y+dy[i]])

	    mem[x][y]=max(mem[x][y],f(x+dx[i],y+dy[i])+1);

	return mem[x][y];

}

int main()

{

	int A,B,C,D; char op[2];

	scanf("%d",&n);

	for(int i=1;i<=n;++i)

	  for(int j=1;j<=n;++j)

	    scanf("%d",&a[i][j]);

	scanf("%d",&m);

	for(;m;--m)

	  {

	  	scanf("%s",op);

	  	if(op[0]=='C')

	  	  {

	  	  	scanf("%d%d%d",&A,&B,&C);

	  	  	a[A][B]=C;

	  	  }

	  	else if(op[0]=='S')

	  	  {

	  	  	scanf("%d%d%d%d",&A,&B,&C,&D);

	  	  	for(int i=A;i<=C;++i)

	  	  	  for(int j=B;j<=D;++j)

	  	  	    cant[i][j]=1;

	  	  }

	  	else if(op[0]=='B')

	  	  {

	  	  	scanf("%d%d%d%d",&A,&B,&C,&D);

	  	  	for(int i=A;i<=C;++i)

	  	  	  for(int j=B;j<=D;++j)

	  	  	    cant[i][j]=0;

	  	  }

	  	else

	  	  {

	  	  	int ans=1;

	  	  	memset(mem,0,sizeof(mem));

	  	  	for(int i=1;i<=n;++i)

	  	  	  for(int j=1;j<=n;++j)

	  	  	    if(!cant[i][j])

	  	  	      ans=max(ans,f(i,j));

	  	  	printf("%d\n",ans);

	  	  }

	  }

	return 0;

}