首页 > 代码库 > uva 1330 City Game (最大子矩阵)
uva 1330 City Game (最大子矩阵)
空白最多的最大子矩阵:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1005; int mat[maxn][maxn],up[maxn][maxn],left[maxn][maxn],right[maxn][maxn]; int main() { int t; scanf("%d",&t); while(t--){ int m,n; scanf("%d%d",&m,&n); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ char 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(lo+1,left[i-1][j]); } } 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(ro-1,right[i-1][j]); int temp = up[i][j]*(right[i][j]-left[i][j]+1); ans=max(ans,temp); } } } printf("%d\n",ans*3); } return 0; }
uva 1330 City Game (最大子矩阵)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。