时间限制: 1 s
空间限制: 64000 KB
题目等级 : 大师 Master
题目描述 Description
有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。
这片土地被分成N*M个格子,每个格子里写着'R'或者'F',R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。 现在freda要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着'F'并且面积最大。 但是rainbow和freda的OI水平都弱爆了,找不出这块土地,而蓝兔也想看freda卖萌(她显然是不会编程的……),所以它们决定,如果你找到的土地面积为S,它们每人给你S两银子。
输入描述 Input Description
第一行两个整数N,M,表示矩形土地有N行M列。 接下来N行,每行M个用空格隔开的字符'F'或'R',描述了矩形土地。
输出描述 Output Description
输出一个整数,表示你能得到多少银子,即(3*最大'F'矩形土地面积)的值。
样例输入 Sample Input
5 6 R F F F F F F F F F F F R R R F F F F F F F F F F F F F F F
样例输出 Sample Output
45
数据范围及提示 Data Size & Hint
对于50%的数据,1<=N,M<=200 对于100%的数据,1<=N,M<=1000
来源:Nescafe 20
一开始天真的以为是搜索后来才发现我错了、、、、
http://www.cnblogs.com/TheRoadToTheGold/p/6217439.html
详解
AC代码
1 #include<cstdio>
2
3 #include<iostream>
4 using namespace std;
5 int n,m,ans;
6 char x;
7 int a[1001][1001],h[1001],leftt[1001],rightt[1001];
8 int main()
9 {
10 scanf("%d%d",&n,&m);
11 for(int i=1;i<=n;i++)
12 for(int j=1;j<=m;j++)
13 {
14 cin>>x;
15 if(x=='R') a[i][j]=1;//1代表有障碍,不能延伸了
16 }
17 for(int j=1;j<=m;j++)//初始化
18 {
19 leftt[j]=1;
20 rightt[j]=m;
21 }
22 for(int i=1;i<=n;i++)//枚举每一行
23 {
24 int l=0,r=m+1;//l向左第一个碰到的障碍,r向右第一个碰到的障碍
25 for(int j=1;j<=m;j++)//从左往右枚举每一列,确定l
26 {
27 if(a[i][j])//当前点是障碍
28 {
29 l=j;//更新向左碰到的第一个障碍
30 h[j]=0;//自本行以下子矩阵高度重新计数
31 leftt[j]=1;//因为left只有一维且以列为下标,所以下一次再用到left[j]是下一行,也就是a[i+1][j],那么由于第i行的阻断,第i+1行不能与前面连成一个矩阵,所以置为最初条件
32 }
33 else//当前点不是障碍,可以参与组成矩阵
34 {
35 h[j]++;//当前列高度+1
36 leftt[j]=max(leftt[j],l+1);//left[i]在更新之前还是第i-1行的结果,所以要从第i-1行和第i行中取大。l+1是因为l存的是R的位置,矩形延伸不能到有障碍的地方
37 }
38 }
39 for(int j=m;j>=1;j--)//同上更新r,确定向右找到的第一个R
40 {
41 if(a[i][j])
42 {
43 r=j;
44 rightt[j]=m;
45 }
46 else
47 rightt[j]=min(rightt[j],r-1);
48 ans=max(ans,(rightt[j]-leftt[j]+1)*h[j]);
49 }
50 }
51 printf("%d",ans*3);
52 }
搜索代码:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=1001;
6 const int maxn=0x7fffffff;
7 int map[MAXN][MAXN];
8 int vis[MAXN][MAXN];
9 int xx[5]={-1,+1,0,0};
10 int yy[5]={0,0,-1,+1};
11 int ans=-1;
12 int maxnnow;
13 int n,m;
14 void dfs(int x,int y)
15 {
16 vis[x][y]=1;
17 for(int i=0;i<4;i++)
18 {
19 int wx=x+xx[i];
20 int wy=y+yy[i];
21 if(vis[wx][wy]==0&&map[wx][wy]==0&&wx>0&&wx<=n&&wy>0&&wy<=m)
22 {
23 maxnnow++;
24 dfs(wx,wy);
25 if(maxnnow>ans)
26 ans=maxnnow;
27 maxnnow=0;
28 }
29 }
30 }
31 int main()
32 {
33
34 scanf("%d%d",&n,&m);
35 for(int i=1;i<=n;i++)
36 {
37 for(int j=1;j<=m;j++)
38 {
39 char c;
40 //scanf("%d",&c);
41 cin>>c;
42 if(c=='R')
43 map[i][j]=1;
44 else
45 map[i][j]=0;
46 }
47 }
48 for(int i=1;i<=n;i++)
49 {
50 for(int j=1;j<=m;j++)
51 {
52 if(vis[i][j]==0)
53 {
54 dfs(i,j);
55 }
56 }
57 }
58 printf("%d",ans*3);
59 return 0;
60 }