分享程序员开发的那些事...
更新时间：2022-06-25 10:31:38
题意：给定一个m*n的矩阵，其中一些个字是空地（F），其他是障碍（R)。找出一个全部由F组成的面积最大的矩阵，输出其面积的3倍。
分析：简单暴力枚举，O（m3*n3)，肯定不行。对于某一块F，设up[i][j]表示其上方的空地个数（就像一条悬线），zl[i][j]表示悬线能往左边走到的边界线的坐标，zr[i][j]表示悬线能往右边走到的边界的坐标，那么面积s=（zr[i][j]-zl[i][j]+1)*up[i][j], zl从左到右枚举可以算出，zr则是从右到左枚举，状态转移是：zl[i][j]=max(zl[i-1][j], lo+1), lo表示第i行中第j列左边的最近障碍物的列编号， zr与之类似，max换成min即可
代码：
1 #include <stdio.h> 2 #include <iostream> 3 using namespace std; 4 #define DEBUG 5 int max(int a, int b){ 6 return a>b?a:b; 7 } 8 int min(int a, int b){ 9 return a<b?a:b; 10 } 11 const int MAXN = 1000 + 10; 12 int mat[MAXN][MAXN], zl[MAXN][MAXN], zr[MAXN][MAXN], up[MAXN][MAXN]; 13 int main(){ 14 #ifndef DEBUG 15 freopen("in.txt", "r", stdin); 16 #endif 17 int cas; 18 scanf("%d", &cas); 19 while(cas--){ 20 int m, n, i, j; 21 scanf("%d%d", &m, &n); 22 for(i=0; i<m; i++){ 23 for(j=0; j<n; j++){ 24 int ch = getchar(); 25 while(ch!='F' && ch!='R') ch=getchar(); 26 if(ch=='F') mat[i][j]=0; 27 else mat[i][j]=1; 28 } 29 } 30 int ans=0; 31 for(i=0; i<m; i++){ 32 int lo=-1, ro=n; 33 for(j=0; j<n; j++){ 34 if(mat[i][j]==1){ 35 zl[i][j]=up[i][j]=0; 36 lo=j; 37 }else{ 38 if(i==0){ 39 up[i][j]=1; 40 zl[i][j]=lo+1; 41 }else{ 42 up[i][j]=up[i-1][j]+1; 43 zl[i][j]=max(zl[i-1][j], lo+1); 44 } 45 } 46 } 47 for(j=n-1; j>=0; j--){ 48 if(mat[i][j]==1){ 49 zr[i][j]=n; 50 ro=j; 51 }else{ 52 if(i==0) zr[i][j]=ro-1; 53 else zr[i][j]=min(zr[i-1][j], ro-1); 54 ans=max(ans, up[i][j]*(zr[i][j]-zl[i][j]+1)); 55 } 56 } 57 } 58 printf("%d\n", ans*3); 59 } 60 return 0; 61 } 62 63 64 65