首页 > > 程序设计 > C/C++ >

bzoj3208--记忆化搜索

2018-06-17 23:28:46来源：未知阅读 ()

题目大意：

花花山峰峦起伏，峰顶常年被雪，Memphis打算帮花花山风景区的人员开发一个滑雪项目。

我们可以把风景区看作一个n*n的地图，每个点有它的初始高度，滑雪只能从高处往低处滑【严格大于】。但是由于地势经常变动【比如雪崩、滑坡】，高度经常变化；同时，政府政策规定对于每个区域都要间歇地进行保护，防止环境破坏。现在，滑雪项目的要求是给出每个n*n个点的初始高度，并给出m个命令，C a b c表示坐标为a,b的点的高度改为c；S a b c d表示左上角为a,b右下角为c,d的矩形地区开始进行保护，即不能继续滑雪；B a b c d表示左上角为a b,右下角为c d的矩形地区取消保护，即可以开始滑雪；Q表示询问现在该风景区可以滑雪的最长路径为多少。对于每个Q要作一次回答。

思路：

由于Q,S,B的次数只有100次，只要暴力做S,B，Q用记忆化搜索就行了。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 inline char Nc(){
 6     static char buf[100000],*p1=buf,*p2=buf;
 7     if(p1==p2){
 8         p2=(p1=buf)+fread(buf,1,100000,stdin);
 9         if(p1==p2)return EOF;
10     }
11     return *p1++;
12 }
13 inline void Read(int& x){
14     char c=Nc(),b=1;
15     for(;c<'0'||c>'9';c=Nc())if(c=='-')b=-1;
16     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc());x*=b;
17 }
18 inline void Read(char& C){
19     char c=Nc();
20     for(;c<'A'||c>'Z';c=Nc());
21     C=c;
22 }
23 int i,j,k,n,m,a[701][701],a1,a2,a3,a4,f[701][701],Ans;
24 int x[4]={-1,1,0,0};
25 int y[4]={0,0,1,-1};
26 bool b[701][701];
27 char C;
28 inline void Dfs(int X,int Y){
29     for(int i=0;i<4;i++)
30     if(x[i]+X&&x[i]+X<=n&&y[i]+Y&&y[i]+Y<=n&&a[X][Y]>a[x[i]+X][y[i]+Y]&&!b[x[i]+X][y[i]+Y]&&f[X][Y]+1>f[x[i]+X][y[i]+Y]){
31         f[x[i]+X][y[i]+Y]=f[X][Y]+1;
32         Dfs(x[i]+X,y[i]+Y);
33     }
34 }
35 int main()
36 {
37     Read(n);
38     for(i=1;i<=n;i++)
39     for(j=1;j<=n;j++)
40     Read(a[i][j]);
41     Read(m);
42     while(m--){
43         Read(C);
44         if(C=='C'){
45             Read(a1);Read(a2);Read(a3);
46             a[a1][a2]=a3;
47         }else if(C=='S'){
48             Read(a1);Read(a2);Read(a3);Read(a4);
49             for(i=a1;i<=a3;i++)
50             for(j=a2;j<=a4;j++)
51             b[i][j]=1;
52         }else if(C=='B'){
53             Read(a1);Read(a2);Read(a3);Read(a4);
54             for(i=a1;i<=a3;i++)
55             for(j=a2;j<=a4;j++)
56             b[i][j]=0;
57         }else{
58             for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=1;
59             for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(!b[i][j]&&f[i][j]==1)Dfs(i,j);
60             for(Ans=0,i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]>Ans)Ans=f[i][j];
61             printf("%d\n",Ans);
62         }
63     }
64     return 0;
65 }