hdu 1505 City Game
8485 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1505
まず、各行のFが底から上へ到達する高さを処理してから、左右に処理する.
View Code
まず、各行のFが底から上へ到達する高さを処理してから、左右に処理する.
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #define maxn 1001
5 using namespace std;
6
7 int t;
8 int n,m;
9 int a[maxn][maxn];
10 int l[maxn],r[maxn];
11
12 int main()
13 {
14 scanf("%d",&t);
15 while(t--)
16 {
17 scanf("%d%d",&n,&m);
18 getchar();
19 memset(a,0,sizeof(a));
20 for(int i=1; i<=n; i++)
21 {
22 for(int j=1; j<=m; j++)
23 {
24 char s[10];
25 scanf("%s",s);
26 if(s[0]=='F') a[i][j]=a[i-1][j]+1;
27 else a[i][j]=0;
28 }
29 }
30 int max1=-1;
31 for(int i=1; i<=n; i++)
32 {
33 a[i][0]=a[i][m+1]=-1;
34 for(int j=1; j<=m; j++)
35 l[j]=r[j]=j;
36 for(int j=1; j<=m; j++)
37 {
38 while(a[i][j]<=a[i][l[j]-1]) l[j]=l[l[j]-1];
39 }
40 for(int j=m; j>=1; j--)
41 {
42 while(a[i][j]<=a[i][r[j]+1]) r[j]=r[r[j]+1];
43 }
44 for(int j=1; j<=m; j++)
45 {
46 int ans=a[i][j]*(r[j]-l[j]+1);
47 if(ans>max1)
48 max1=ans;
49 }
50 }
51 printf("%d
",max1*3);
52 }
53 return 0;
54 }
View Code