UVa 1330 - City Game

题意

找出最大空的子矩阵。

思路

直接枚举复杂度太高。

可以把每个格子向上延伸的连续空格看成一条线,然后表示出他的左右运动极限。然后算出面积。

代码

#include <cstdio>
#include <algorithm>
#include <functional>
#include <stack>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <map>
#include <cmath>
#define LL long long
#define lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(arr, num) memset(arr, num, sizeof(arr))
#define PB push_back
#define ROP freopen("input.txt", "r", stdin);
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
using namespace std;
const int MAXN = 1000 + 5;
 
struct POINT
{
    int l, r, up;
}pit[MAXN][MAXN];
 
char mp[MAXN][MAXN];
 
int main()
{
    //ROP;
    int T, i, j, row, col, pos;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%*c", &row, &col);
        for (i = 1; i <= row; i++)
            for (j = 1; j <= col; j++)
            {
                char ch = getchar();
                while (ch != 'R' && ch != 'F') ch = getchar();
                mp[i][j] = ch;
            }
        int ans = 0;
        for (i = 1; i <= row; i++)
        {
            int lpos = 0, rpos = col + 1;
            for (j = 1; j <= col; j++)
            {
                if (mp[i][j] == 'R')
                {
                    pit[i][j].l = 1; pit[i][j].up = 0;
                    lpos = j;
                }
                else
                {
                    pit[i][j].up = (i == 1 ? 1 : pit[i - 1][j].up + 1);
                    pit[i][j].l = (i == 1 ? lpos + 1 : max(pit[i - 1][j].l, lpos + 1));
                }
            }
            for (j = col; j >= 1; j--)
            {
                if (mp[i][j] == 'R')
                {
                    pit[i][j].r = col;
                    rpos = j;
                }
                else
                {
                    pit[i][j].r = (i == 1 ? rpos - 1 : min(pit[i - 1][j].r, rpos - 1));
                    ans = max(ans, (pit[i][j].r - pit[i][j].l + 1) * pit[i][j].up);
                }
            }
        }
        printf("%d\n", ans * 3);
    }
    return 0;
}

Powered by Jekyll and Theme by solid