uva 1330 City Game

클릭하여 링크 열기uva1330
사고방식: 현선법 구해 최대 서브매트릭스 분석: 1 상세한 자료는 클릭하여 링크 열기2 입력 형식에 주의해야 할 부분이 있는데 자모 뒤에 여러 개의 빈칸이 있을 수 있기 때문에 반드시 이 빈칸 코드를 필터해야 한다.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1010;
int mat[MAXN][MAXN];
int up[MAXN][MAXN] , Left[MAXN][MAXN] , Right[MAXN][MAXN];
int n , m;

int solve(){
    int ans = 0;
    int leftNum , rightNum;
    for(int i = 1 ; i <= n ; i++){
       //             
       leftNum = 0;
       for(int j = 1 ; j <= m ; j++){
          if(!mat[i][j]){
             up[i][j] = 0; 
             Left[i][j] = 0;
             leftNum = j;
          }
          else{
             up[i][j] = i == 1 ? 1 : up[i-1][j]+1;   
             Left[i][j] = i == 1 ? leftNum+1 : max(Left[i-1][j] , leftNum+1); 
          } 
       }
       //             
       rightNum = m+1;
       for(int j = m ; j >= 1 ; j--){
          if(!mat[i][j]){ 
             Right[i][j] = m+1; 
             rightNum = j;
          }
          else{
             Right[i][j] = i == 1 ? rightNum-1 : min(Right[i-1][j] , rightNum-1);
             ans = max(ans , up[i][j]*(Right[i][j]-Left[i][j]+1));
          }
       }
    }
    return 3*ans;
}

int main(){
    int Case;
    char c;
    scanf("%d" , &Case);
    while(Case--){
        scanf("%d%d" , &n , &m);
        for(int i = 1 ; i <= n ; i++){
           for(int j = 1 ; j <= m ; j++){
               c = getchar();
               while(c != 'F' && c != 'R')
                   c = getchar();
               mat[i][j] = c == 'F' ? 1 : 0;
           }
        }
        printf("%d
" , solve()); 
    }
    return 0;
}