本文主要是介绍POJ - 1964 City Game,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:给定一个m*n的矩阵,其中一些格子是空地F,其他的是障碍R,找出一个最大的全部有F组成的面积最大的矩阵,输出面积乘以3的结果
思路: 用简单的枚举左上角坐标,长,宽显然是会超时的,这里有一种求极大子矩阵问题的方法:用up(i,j),left(i,j),right(i,j)分别表示某个点的最大的上连续的空地长度和向左可以得到相同up的最大宽度,以及向右可以得到的相同up的最大宽度,还用lo,ro分别表示距离左右的最近障碍的列
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000;int mat[MAXN][MAXN],up[MAXN][MAXN],Left[MAXN][MAXN],Right[MAXN][MAXN];int main(){int t;scanf("%d",&t);while (t--){int n,m;scanf("%d%d%*c",&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++)if (mat[i][j] == 1){up[i][j] = Left[i][j] = 0;lo = j;}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--)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;
}
这篇关于POJ - 1964 City Game的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!