题解 P3135 【[USACO16JAN]堡哞Fort Moo】

Celebrate · 2018-12-05 13:27:28 · 题解

宣传一下我的博客

看到这一题，就感觉是用O(n^3)的做法

因为这一题要找一个矩形框架，我们知道要找框架需要固定两条边，然后从中间开始找

所以先枚举两列，然后枚举行，如果可行就更新最大值

代码（我的代码可能和其他题解有些不一样）

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std ;
inline int read() { //快读 
    int x = 0 , f = 0 ; char s = getchar() ;
    while ( !isdigit(s) ) s = getchar() ;
    while (  isdigit(s) ) x = (x<<1) + (x<<3) + s - 48 , s = getchar() ;
    return !f ? x : -x ;
}
const int N = 210 ;
int n , m ;
int sum[N][N] ; //第i行的前缀和 
char st[N] ;
int query( int i , int x , int y ) { return sum[i][y] - sum[i][x-1] ; } //查询第i行从x到y的和 
int maxx = 0 ;
int main() {
    n = read() , m = read() ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        scanf ( "%s" , st+1 ) ;
        for ( int j = 1 ; j <= m ; j ++ ) //前缀和 
            sum[i][j] = sum[i][j-1] + ( st[j] == '.' ? 0 : 1 ) ;
    }
    for ( int l = 1 ; l <= m ; l ++ ) //枚举两列 
        for ( int r = l ; r <= m ; r ++ ) {
            int last = 1 ; //last表示上一个全部为非沼泽地区的行 
            while ( last < n && query(last,l,r) != 0 ) last ++ ; //找第一个 
            if( query(last,l,r) != 0 ) continue ; // 如果没有就离开 
            for ( int i = last ; i <= n ; i ++ ) { //枚举行 
                if( query(i,l,l) != 0 || query(i,r,r) != 0 ) { //如果这两个点又沼泽（说明这个框架不能到达这里） 
                    last = i + 1 ; // 找下一个满足条件的行 
                    while ( last < n && query(last,l,r) != 0 ) last ++ ;
                    if( query(last,l,r) != 0 ) break ;//如果没有满足条件的行 
                }
                else {
                    if ( query(i,l,r) == 0 ) //如果能够形成框架 
                        maxx = max( maxx , (r-l+1) * (i-last+1) ) ; //更新最大值 
                }
            }
        }
    printf( "%d\n" , maxx ) ;
    return 0 ; 
}