QBSQUARE spoj - Hình vuông 0 1

Nguồn đề bài: QBSQUARE

1. Đề bài QBSQUARE 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 vuông gồm các ô của bảng thoả mãn các điều kiện sau:
1 – Hình vuông là đồng nhất: tức là các ô thuộc hình vuông đó phải ghi các số giống nhau (0 hoặc 1)
2 – Cạnh hình vuông song song với cạnh bảng.
3 – Kích thước hình vuông 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 kích thước cạnh của hình vuông 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:
7

2. Code tham khảo QBSQUARE spoj

a. Code c++

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=1005;
int n,m,a[maxn][maxn],f[maxn][maxn];

void Init()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            f[i][j]=1;
        }
}

int min(int a, int b, int c)
{
    a=min(a,b);
    return min(a,c);
}
void Solve()
{
    int res=0;
    for(int i=2;i<=m;i++)
        for (int j=2;j<=n;j++)
        {
            if(a[i][j]==a[i-1][j-1] && a[i][j]==a[i-1][j] && a[i][j]==a[i][j-1])
                f[i][j]=min(f[i-1][j-1], f[i-1][j], f[i][j-1])+1;
            if(f[i][j]>res) res=f[i][j];
        }
        cout<<res;
}
int main()
{
    Init();
    Solve();
}

b. Code pascal

const   fi='';
        nmax=1000;
type    data=longint;
var
        f:text;
        A:Array[0..nmax+1,0..nmax+1] of byte;
        S,L,R,D:array[0..nmax*nmax+1] of data;
        n,m,sta,res: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;

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

procedure layra;
begin
        dec(sta);
end;

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

function min(a,b:data):data;
begin
        if a>b then exit(b);
exit(a);
end;

function max(a,b:data):data;
begin
        if a>b then
                exit(a);
        exit(b);
end;

procedure xuli(k:data);
var     kq,dientich,i,j:data;
begin
        for i:=1 to n do
                d[i]:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                if a[i,j]<>k then
                                        d[j]:=i;
                        sta:=0;
                        for j:=1 to n do
                                begin
                                        while (sta>0) and (D[xem]<=d[j]) do
                                                layra;
                                        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
                                                layra;
                                        if sta=0 then
                                                R[j]:=n+1
                                        else
                                                R[j]:=xem;
                                        them(j);
                                end;
                        for j:=1 to n do
                                res:=max(res,min((i-d[j]),(R[j]-L[j]-1)));
                end;
end;

begin
        docfile;
        res:=0;
        xuli(1);
        xuli(0);
        writeln(res);
end.

QBSQUARE spoj – Hình vuông 0 1