BZOJ 3039 玉蟾宮 懸線法

BZOJ 3039 玉蟾宮 懸線法

題目大意：給出一張地圖，求出這張地圖中最大的子矩陣，使得這個子矩陣不包含字母‘R’。

思路：簡單的懸線法求最大子矩陣，還是不帶權值的，很好求。好久沒寫懸線了，復習一下。

CODE：

#include 
#include 
#include 
#include 
#define MAX 1010
using namespace std;
 
int m,n;
bool map[MAX][MAX];
int max_left[MAX][MAX],max_right[MAX][MAX];
int max_up[MAX][MAX];
 
inline char GetChar()
{
    char c;
    while(c = getchar(),c == ' ' || c == '\n' || c == '\t' || c == '\r');
    return c;
}
 
int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            map[i][j] = GetChar() == 'F';
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j)
            max_left[i][j] = !map[i][j] ? 0:max_left[i][j - 1] + 1;
        for(int j = n; j; --j)
            max_right[i][j] = !map[i][j] ? 0:max_right[i][j + 1] + 1;
    }
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            if(map[i][j] && map[i - 1][j]) {
                max_up[i][j] = max_up[i - 1][j] + 1;
                max_left[i][j] = min(max_left[i][j],max_left[i - 1][j]);
                max_right[i][j] = min(max_right[i][j],max_right[i - 1][j]);
            }
    int ans = 0;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            ans = max(ans,(max_left[i][j] + max_right[i][j] - 1) * (max_up[i][j] + 1));
    cout << ans * 3 << endl;
    return 0;
}