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;
}
- 上一篇STL使用小记
- 下一篇UVa 1346 - Songs