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

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

Nội dung bài viết

Đề bài QBRECT spoj
THUẬT TOÁN
- code pascal
- code c++

Đề 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.

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;

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);
}

#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”

Nguyễn Hữu Vinh says:
24 Tháng Mười Một, 2015 at 14:52
bài viết gì mà thuật toán với code kí hiệu lung tung beng xà quần làm người đọc khó hiểu!! @@~
Trả lời
- kudoshinichilike says:
  30 Tháng Mười Một, 2015 at 12:27
  :v mỗi ng có 1 cách code riêng thôi mà!
  Trả lời
  - Admin says:
    30 Tháng Mười Một, 2015 at 17:18
    Tụi nó bạn anh á em, tụi nó trolll ý :v
    Trả lời
    - kudoshinichilike says:
      1 Tháng Tư, 2016 at 00:03
      :v
      Trả lời
Nguyễn Hữu Vinh says:
24 Tháng Mười Một, 2015 at 14:53
xin lỗi! đặt biến chứ không phải kí hiệu, đặt biến lung tung lộn xộn rối beng rối nùi hà~~
Trả lời
Park Soung Hip says:
24 Tháng Mười Một, 2015 at 14:58
What’s a very very bad and borin’ post! I don’t know what r u talkin’ about… The explainations is too complex
Trả lời
- Nguyễn Hữu Vinh says:
  24 Tháng Mười Một, 2015 at 15:00
  (LIKE)
  Trả lời
Bookmark says:
31 Tháng Ba, 2016 at 17:46
Bài này nếu giải bằng QHĐ thì phải chia ra 2 lần tính như dãy lồi, tính chiều dài và chiều rộng hả a? Hay là có CT QHĐ ạ????
Trả lời
trần tuấn đạt says:
5 Tháng Mười Hai, 2016 at 22:25
thế ban đầu h[j] bằng bao nhiêu thế,vs j=1 ý
Trả lời

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

Đề bài QBRECT spoj

Input

Output

Example

THUẬT TOÁN

code pascal

code c++

Bài viết liên quan

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

Trả lời Hủy