USACO 6.1.2 矩形牛棚

 

一两周不做题了，做个题维护下大脑。

 

到底是个资本家，Farmer John想通过买更多的奶牛来扩大它的生意。它需要给奶牛建造一个新的牛棚。FJ买了一个矩形的R(1 <= R <= 3000)行C(1 <= C <= 3000)列的牧场。不幸的是，他发现某些1 x 1的区域被损坏了，所以它不可能在把整个牧场建造成牛棚了。FJ数了一下，发现有P(1 <= p <= 30000)个1 x 1的损坏区域并且请你帮助他找到不包含损坏区域的面积最大的矩形的牛棚。 输入格式（file rectbarn.in）

第1行: 三个空格隔开的整数 R, C, and P.

第2..P+1行: 每行包含两个空格隔开的整数, r和c, 给出一个损坏区域的行号和列号.

样例输入

3 4 2

 1 3

 2 1

输出格式（file rectbarn.out）

第1行: 牛棚的最大可能面积

样例输入3 4 2 1 3 2 1

样例输出6

输出解释

  1 2 3 4
.+-+-+-+-+
1| | |X| |
.+-+-+-+-+
2|X|#|#|#|
.+-+-+-+-+
3| |#|#|#|
.+-+-+-+-+

标'X'的区域是损坏的, 标 '#'的区域是牛棚.

解析：

该题是USACO 3.4巨大牛棚的升级版。核心思想可参考这里。实际这个题比3.4还是难了许多，更多循环，更复杂的判断。

http://blog.chinaunix.net/uid-26456800-id-3273510.html

 

3.4题目中是正方形，这个是矩形，所以对于每个点来说，向左上方向可扩充形成的最大矩形就有了2种可能。一种是横向尽可能长，一种是纵向尽可能高。

用两个矩阵分别记录两种方向扩张产生矩形的长和高，最后选择出面积最大的即可。

下面的示例程序输出了两种方向扩展产生的不同结果，可以依照输出来理解算法。

 

还有要注意一下的地方是因为输如数据的规模还比较大，有3000*3000，为了节省空间，使用char来表示输入信息比int节省3/4的空间

 

复杂度：

O(R*C),线性复杂度

 

#include <stdlib.h>
#include <stdio.h>
#define MAX 3000
#define min(a, b) (a)>(b)?(b):(a)
#define max(a, b) (a)<(b)?(b):(a)

typedef struct tagRect{
    int L;
    int H;
} Rect;

Rect* lresult[MAX][MAX];
Rect* hresult[MAX][MAX];

void test(char input[][MAX], int len, int height){
    int row, col;
    for(row = 0; row < height; row++){
        for(col = 0; col< len; col++){
            Rect* t = (Rect*)malloc(sizeof(Rect));
            t->L = t->H = 0;
            lresult[row][col] = t;
            if(input[row][col] == 1){
                continue;
            }
            else{
                if(col-1>=0){
                    t->L = lresult[row][col-1]->L+1;
                    t->H = lresult[row][col-1]->H;
                }
                else{
                    t->L = col+1;
                    t->H = row+1;
                }
                if(row-1>=0){
                    t->H = min(t->H, lresult[row-1][col]->H+1);
                    if(t->H == 0){
                        t->H = lresult[row-1][col]->H+1;
                    }
                }
                if(t->H == 0){
                    t->H = 1;
                }
            }
        }
    }

    for(row = 0; row < height; row++){
        for(col = 0; col< len; col++){
            Rect* t = (Rect*)malloc(sizeof(Rect));
            t->L = t->H = 0;
            hresult[row][col] = t;
            if(input[row][col] == 1){
                continue;
            }
            else{
                if(row-1>=0){
                    t->L = hresult[row-1][col]->L;
                    t->H = hresult[row-1][col]->H+1;
                }
                else{
                    t->L = col+1;
                    t->H = row+1;
                }
                if(col-1>=0){
                    t->L = min(t->L, hresult[row][col-1]->L+1);
                    if(t->L == 0){
                        t->L = hresult[row][col-1]->L+1;
                    }
                }
                if(t->L == 0){
                    t->L = 1;
                }
            }
        }
    }

}
void output(Rect* tmp[MAX][MAX], int len, int height){
    int i, j;
    for(i = 0; i<height; i++){
        for(j = 0; j<len; j++){
            printf(" (%d, %d)",tmp[i][j]->L, tmp[i][j]->H);
        }
        printf("\n");
    }
}
int getMax(int len, int height){
    int result = 0;
    int i,j;
    for(i = 0; i<height; i++){
        for(j = 0; j<len; j++){
            result = max(result, max(lresult[i][j]->H * lresult[i][j]->L,
                        hresult[i][j]->H * hresult[i][j]->L));


        }
    }
}


int main(){
    char input[MAX][MAX] = {{0}};
    int len = 4;
    int height = 4;
    input[0][2] = 1;
    input[1][0] = 1;
    test(input, len, height);
    output(lresult, len ,height);
    printf("-------------------\n");
    output(hresult, len ,height);
    printf("max = %d \n", getMax(len, height));
}