QBRECT spoj – Hình chữ nhật 0 1

Nguồn đề bài: http://vn.spoj.com/problems/QBRECT/

Đề bài QBRECT spoj

Cho một bảng kích thước MxN, được chia thành lưới ô vuông đơn vị M dòng N cột ( 1 <= M, N <= 1000 )

Trên các ô của bảng ghi số 0 hoặc 1. Các dòng của bảng được đánh số 1, 2… M theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số 1, 2…, N theo thứ tự từ trái qua phải

Yêu cầu:

Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:

1 – Hình chữ nhật đó chỉ gồm các số 1

2 – Cạnh hình chữ nhật song song với cạnh bảng

3 – Diện tích hình chữ nhật là lớn nhất có thể

Input

Dòng 1: Ghi hai số M, N

M dòng tiếp theo, dòng thứ i ghi N số mà số thứ j là số ghi trên ô (i, j) của bảng

Output

Gồm 1 dòng duy nhất ghi diện tích của hình chữ nhật tìm được

Example

Input:
11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1

Output:
49

THUẬT TOÁN

code pascal

const   fi='';
        nmax=1000;
type    data=longint;
var
        f:text;
        A:array[0..nmax+1,0..nmax+1] of byte;
        n,test,m:data;
        sta:data;
        H:array[0..nmax*nmax+1] of data;
        D,L,R:array[0..nmax+1] of data;


procedure docfile;
var     i,j:data;
begin
        assign(f,fi);reset(f);
        readln(f,m,n);
        for i:=1 to m do
                for j:=1 to n do
                        read(f,a[i,j]);
        close(f);
end;

function xem:data;
begin
        exit(h[sta]);
end;

procedure them(x:data);
begin
        inc(sta);
        h[sta]:=x;
end;

function lay:data;
begin
        lay:=h[sta];
        dec(sta);
end;

procedure xuli;
var     i,j,res,dt:data;
begin
        fillchar(d,sizeof(d),0);
        res:=0;
        sta:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                if a[i,j]<>1 then
                                        d[j]:=i;
                        sta:=0;
                        for j:=1 to n do
                                begin
                                        while (sta>0) and (D[xem]<=D[j]) do
                                                lay;
                                        if sta=0 then
                                                L[j]:=0
                                        else
                                                L[j]:=xem;
                                        them(j);
                                end;
                        sta:=0;
                        for j:=n downto 1 do
                                begin
                                        while (sta>0) and (d[xem]<=d[j]) do
                                                lay;
                                        if sta=0 then
                                                R[j]:=n+1
                                        else
                                                R[j]:=xem;
                                        them(j);
                                end;
                        for j:=1 to n do
                                begin
                                        dt:=(i-d[j])*(R[j]-L[j]-1);
                                        if dt>res then
                                                res:=dt;
                                end;
                end;
        writeln(res);
end;

begin
        docfile;
        xuli;
        readln;
end.

code c++

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

#define maxn        1010

int     n , m , a[maxn][maxn];
int     h[maxn] , l[maxn] , r[maxn] , res;

int main()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++) scanf("%d",&a[i][j]);
    h[0] = -1; h[n+1] = -1;
    for (int i=1;i<=m;i++) {
        for (int j=1;j<=n;j++)
            h[j] = a[i][j] * (h[j] + 1);
        for (int j=1;j<=n;j++) {
            l[j] = j;
            while (h[l[j]-1] >= h[j]) l[j] = l[l[j]-1];
        }
        for (int j=n;j>0;j--) {
            r[j] = j;
            while (h[r[j]+1] >= h[j]) r[j] = r[r[j]+1];
        }
        for (int j=1;j<=n;j++)
            res = max(res,h[j]*(r[j]-l[j]+1));
    }
    printf("%d",res);
}

 

9 thoughts on “QBRECT spoj – Hình chữ nhật 0 1

  1. Bài này nếu giải bằng QHĐ thì phải chia ra 2 lần tính như dãy lồi, tính chiều dài và chiều rộng hả a? Hay là có CT QHĐ ạ????

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *