1.题目描述:点击打开链接
2.解题思路:本题利用扫描法解决:从上向下扫描每一行,如果我们把每个格子向上延伸的连续空格看做一条悬线,并用up(i,j),left(i,j),right(i,j)表示格子(i,j)的悬线长度以及该悬线向左,向右能够运动的“运动极限”,即最远能够走到哪一列。这样,每个格子(i,j)对应着一个以第i行为下边界,高度为up(i,j),宽度为right(i,j)-left(i,j)的矩形,那么这些矩形中的面积最大值就是题目所求。因此,关键是如何快速的求出这三个数值。
当格子(i,j)不是空格时,3个数组的值均为0,否则up(i,j)=up(i-1,j)+1。同样可以找到left的递推公式:left(i,j)=max{left(i-1,j),lo+1}(lo表示第i行目前最近的障碍格的列编号)如果从左往右扫描,则很容易维护lo。right的算法类似,但需要从右往左扫描。
3.代码:
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<string> #include<sstream> #include<set> #include<vector> #include<stack> #include<map> #include<queue> #include<deque> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #include<functional> using namespace std; #define N 1000 int mat[N][N], up[N][N], Left[N][N], Right[N][N]; int main() { //freopen("t.txt", "r", stdin); int T; cin >> T; while (T--) { int m, n; cin >> m >> n; for (int i = 0; i < m;i++) for (int j = 0; j < n; j++) { int ch = getchar(); while (ch != 'F'&&ch != 'R')ch = getchar(); mat[i][j] = ch == 'F' ? 0 : 1; } int ans = 0; for (int i = 0; i < m; i++)//从上到下逐行处理 { int lo = -1, ro = n; for (int j = 0; j < n;j++)//从左到右扫描,维护up和left if (mat[i][j] == 1)//有障碍物 { up[i][j] = Left[i][j] = 0; lo = j;//第i行目前最近的障碍格的列编号 } else { up[i][j] = i == 0 ? 1 : up[i - 1][j] + 1;//先判断,后赋值 Left[i][j] = i == 0 ? lo + 1 : max(Left[i - 1][j], lo + 1); } for (int j = n - 1; j >= 0; j--)//从右往左扫描,维护right并更新答案 if (mat[i][j] == 1) { Right[i][j] = n; ro = j; } else { Right[i][j] = i == 0 ? ro - 1 : min(Right[i - 1][j], ro - 1); ans = max(ans, up[i][j] * (Right[i][j] - Left[i][j] + 1)); } } printf("%d\n", ans * 3); } return 0; }