HDU 1505 & POJ 1964 City Game (递推+扫描法)

题意：一个矩阵，有些格子是F，有些是R，要你找到最大的子矩阵使得矩阵内全是F

思路:直接枚举每个子矩阵，显然复杂度是O(m^3 n^3)，显然TLE。

我们可以使用扫描法：用up(i,j)表示格子(i,j)悬垂线(悬垂线就是指这个格子往上走遇到第一个R的格子之前的线段)的长度。left(i,j)表示悬垂线往左扫最左能移动到的位置(遇到R会停止)，right(i,j)表示悬垂线往右扫最右能移动到的位置(遇到R会停止)。那么格子(i,j)可以对应一个这样的最大F矩形：以第i行作为底边，第i-up(i,j)+1行作为上底边，left(i,j)所在列为左边，right(i,j)所在列作为右边的矩形。

那么最终答案就是每个格子对应的矩形中的最大值。

up(i,j)可以用递推式：（1）若map[i][j]=='F'，up(i,j)=up(i-1,j)+1 （2）若map[i][j]=='R'，up(i,j)=0

left(i,j)可以用递推式：（1）若map[i][j]=='F'，left(i,j)=max{left(i-1,j),lo+1} (lo是格子(i,j)左边最近的'R'的列)（2）若map[i][j]=='R'，left(i,j)=0

right(i,j)可以用递推式：（1）若map[i][j]=='F'，right(i,j)=max{right(i-1,j),ro-1} (ro是格子(i,j)右边最近的'R'的列)（2）若map[i][j]=='R'，right(i,j)=n

注意：这个题目读入数据规模较大，用scanf会TLE。。。。getchar()才行。。。

#include
#include
#define MAXN 1005
using namespace std;
int T,n,m,righ[MAXN][MAXN],up[MAXN][MAXN],lef[MAXN][MAXN];
char map[MAXN][MAXN];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        int ans=0;
        scanf("%d%d",&m,&n); getchar();
        for(int i=0;i=0;--j)
            if(map[i][j]=='R') ro=j,righ[i][j]=n;
            else righ[i][j]=i  min(ro-1,righ[i-1][j]):ro-1;//递推right(i,j)

        for(int i=0;i