Editorial for Hình vuông 0 1


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

var t,k:byte;
    m,n,i,j,max:integer;
    a:array[0..1,0..1,1..5000] of integer;

procedure wr;
begin
     writeln(max);
end;

function min(x,y,z:integer):integer;
begin
     if (x<=y) and (x<=z) then min:=x
     else
     begin
          if y<=z then min:=y else min:=z;
     end;
end;

begin
     readln(m,n);
     fillchar(a,sizeof(a),0);
     max:=0; 
     for i:=1 to m do
     begin
          t:=i mod 2;
          for j:=1 to n do
          begin
               read(k);
               if k=1 then
               begin
                    a[t,0,j]:=0;
                    a[t,1,j]:=min(a[1-t,1,j-1],a[1-t,1,j],a[t,1,j-1])+1;
                    if a[t,1,j]>max then
                    begin
                         max:=a[t,1,j];

                    end;
               end
               else
               begin
                    a[t,1,j]:=0;
                    a[t,0,j]:=min(a[1-t,0,j-1],a[1-t,0,j],a[t,0,j-1])+1;
                    if a[t,0,j]>max then
                    begin
                         max:=a[t,0,j];
                    end;
               end;
          end;
          readln;
     end;
     wr;
end.

Code mẫu của happyboy99x

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

#define N 1000
int dp[N+1][N+1], a[N+1][N+1], m, n;

inline int get(int a, int b, int c, int d) {
    return dp[c][d] - dp[a][d] - dp[c][b] + dp[a][b];
}

int main() {
    scanf("%d%d",&m,&n);
    int res = 0;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j) {
            scanf("%d", &a[i][j]); dp[i][j] = 1;
            if(a[i][j] == a[i-1][j] && a[i-1][j] == a[i-1][j-1] && a[i-1][j-1] == a[i][j-1])
                res = max(res, dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]))+1);
        }
#ifdef __WATASHI 
    putchar(10); for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) printf("%d ", dp[i][j]);
        putchar(10);
    }
#endif
    printf("%d\n", res);
    return 0;
}

Code mẫu của ladpro98

program qbrect;
uses    math;

type    bin = 0..1;
var     f:array[-1..1001] of longint;
        a:array[0..1001,0..1001] of bin;
        i,maxS,m,n,j,target:longint;
        inp:text;

procedure input;
var     i,j:longint;
begin
        assign(inp,'');
        reset(inp);
        readln(inp,m,n);
        for i:=1 to m do
        begin
                for j:=1 to n do read(inp,a[i,j]);
        end;

end;

procedure process(row:longint);
var     i,j:longint;
        l,r:array[-2..1002] of longint;
begin
        fillchar(l,sizeof(l),0);
        fillchar(r,sizeof(r),0);
        for i:=1 to n do
        if a[row,i] = target then inc(f[i])
                else f[i]:=0;
        l[1]:=0;
        for i:=2 to n do
        begin
                j:=i-1;
                while (j>0) and (f[j]>=f[i]) do
                    j:=l[j];
                l[i]:=j;
        end;
        r[n]:=n+1;
        for i:=n-1 downto 1 do
        begin
                j:=i+1;
                while (j<n+1) and (f[j]>=f[i]) do
                        j:=r[j];
                r[i]:=j;
        end;

        for i:=1 to n do
        begin
                if f[i]>0 then
                maxS:=max(maxS,min(r[i]-l[i]-1,f[i]));
        end;
end;

begin
        fillchar(a,sizeof(a),0);
        input;
        maxS:=0;
        for i:=1 to m do
        process(i);
        target:=1;
        for i:=1 to m do
        process(i);
        write(maxS);
end.

Code mẫu của RR

uses math;
var
  i,j,top,res,m,n:longint;
  a:array[0..1011,1..1011] of longint;
  down,left,right,stack:array[0..1011] of longint;

procedure solve(k:longint);
    var
      i,j:longint;
    begin
      down[0]:=0;
      down[n+1]:=down[0];
      for i:=1 to m do
        begin
          for j:=1 to n do
            if a[i,j]=k then down[j]:=down[j]+1
            else down[j]:=0;

          top:=0; stack[0]:=0;
          for j:=1 to n do
            begin
              while (top>0) and (down[stack[top]]>=down[j]) do dec(top);
              left[j]:=stack[top]+1;
              inc(top); stack[top]:=j;
            end;

          top:=0; stack[0]:=n+1;
          for j:=n downto 1 do
            begin
              while (top>0) and (down[stack[top]]>=down[j]) do dec(top);
              right[j]:=stack[top]-1;
              inc(top); stack[top]:=j;
            end;

          for j:=1 to n do
            res:=max(res,min(down[j],right[j]-left[j]+1));
        end;
    end;

begin
  read(m,n);
  for i:=1 to m do
  for j:=1 to n do
    read(a[i,j]);

  solve(0);
  solve(1);
  writeln(res);
end.

Code mẫu của hieult

#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
//#include<conio.h>

using namespace std;

#define FOR(i, a, b) for(int i=(a), _b=(b); i < _b; ++i)
#define FORU(i, a, b) for(int i=(a), _b=(b); i <= _b; ++i)
#define FORD(i, a, b) for(int i=(a), _b=(b); i >= _b; --i)
#define maxn 1111

int l[2][maxn], r[2][maxn], h[2][maxn], a[maxn][maxn];

int main(){
    //freopen("QBRECT.in","r",stdin);
     int m,n,kq = 0;
     scanf("%d %d",&m,&n);
     FORU(i, 1, m) FORU(j, 1, n) scanf("%d",&a[i][j]);
     memset(h,0,sizeof(h));
     FORU(i, 1, m) FOR(t, 0, 2){
          FORU(j, 1, n) {
               if(a[i][j]==t)
                     h[t][j]++;
               else h[t][j] = 0;
          }
          h[t][0] = -1; h[t][n+1] = -1;
          FORU(j, 1, n){
               l[t][j] = j;
               while(h[t][l[t][j]-1]>=h[t][j]) l[t][j] = l[t][l[t][j]-1];
          }
          FORD(j, n, 1){
               r[t][j] = j;
               while(h[t][r[t][j]+1]>=h[t][j]) r[t][j] = r[t][r[t][j]+1];
          }
          FORU(j, 1, n){
               kq = max(kq,min(h[t][j],r[t][j]-l[t][j]+1));
          }
     }
     printf("%d",kq);
     //getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
Program QBSQUARE;
Const
  input  = '';
  output = '';
  maxn = 1000;
Type
  rec = record
    n0,n1: integer;
  end;
Var
  n,m,max: integer;
  a: array[1..maxn,1..maxn] of integer;
  F: array[0..maxn,0..maxn] of rec;
  ch: boolean;

Procedure init;
Var
  fi: text;
  i,j: integer;
Begin
  Assign(fi, input);
    Reset(fi);

  Readln(fi, m, n);
  For i:= 1 to m do
    For j:= 1 to n do read(fi, a[i,j]);

  Close(fi);
End;

Procedure gens;
Var
  t0,t1,i,j: integer;
Begin
  Fillchar(F[0], sizeof(F[0]), 0);
  For i:= 1 to m do
    Begin
      t0:= 0;
      t1:= 0;

      For j:= 1 to n do
        Begin
          If a[i,j] = 0 then inc(t0) else inc(t1);
          F[i,j].n0:= F[i - 1,j].n0 + t0;
          F[i,j].n1:= F[i - 1,j].n1 + t1;
        End;
    End;
End;

Function calc(x,y,z,t: integer): rec;
Var
  u: rec;
Begin
  u.n0:= F[z,t].n0 - F[z,y - 1].n0 - F[x - 1,t].n0 + F[x - 1,y - 1].n0;
  u.n1:= F[z,t].n1 - F[z,y - 1].n1 - F[x - 1,t].n1 + F[x - 1,y - 1].n1;
  calc:= u;
End;

Procedure solve;
Var
  i,j: integer;
  t: rec;
Begin
  ch:= false;
  max:= 1;

  For i:= 1 to m do
    For j:= 1 to n do
      If (i + max <= m) and (j + max <= n) then
        Begin
          t:= calc(i,j,i + max,j + max);
          If t.n0 * t.n1 = 0 then
            Begin
              ch:= true;
              While (i + max < m) and (j + max < n) and (t.n0 * t.n1 = 0) do
                Begin
                  t:= calc(i,j,i + max + 1,j + max + 1);
                  If t.n0 * t.n1 = 0 then inc(max);
                End;
            End;
        End;
End;

Procedure printresult;
Var
  fo: text;
Begin
  Assign(fo, output);
    Rewrite(fo);
    If not ch then writeln(fo, 1) else writeln(fo, max + 1);
  Close(fo);
End;

Begin
  init;
  gens;
  solve;
  printresult;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   1111
int a[MAX][MAX];
int f[MAX][MAX];
int m,n;
int min(int x,int y,int z)
{
    int m;
    m=x;
    if (y<m) m=y;
    if (z<m) m=z;
    return (m);
}
void init(void)
{
     int i,j;
     scanf("%d",&m);
     scanf("%d",&n);
     for (i=1;i<=m;i=i+1)
         for (j=1;j<=n;j=j+1)
             scanf("%d",&a[i][j]);
}
void optimize(void)
{
     int i,j,s,r;
     for (i=1;i<=m;i=i+1) f[i][1]=1;
     for (i=1;i<=n;i=i+1) f[1][i]=1;
     for (i=2;i<=m;i=i+1)
         for (j=2;j<=n;j=j+1)
             {
              s=a[i][j]+a[i][j-1]+a[i-1][j]+a[i-1][j-1];
              if (s*(s-4)==0) f[i][j]=min(f[i][j-1],f[i-1][j],f[i-1][j-1])+1;
              else f[i][j]=1;
             }
     r=0;
     for (i=1;i<=m;i=i+1)
         for (j=1;j<=n;j=j+1)
             if (r<f[i][j]) r=f[i][j];
     printf("%d\n",r);
}
int main(void)
{
    init();
    optimize();
}

Code mẫu của khuc_tuan

#include <stdio.h>

int m, n;
int h0[1000], h1[1000], l1[1000], l0[1000];

int main() {
    int i, j, xx, t, result = 0;
    scanf("%d%d", &m, &n);
    for(i=0;i<m;++i) {
        t = 0;
        for(j=0;j<n;++j) {
            scanf("%d", &xx);
            h1[j] = (xx==1) ? h1[j]+1 : 0;
            h0[j] = (xx==0) ? h0[j]+1 : 0;
            l1[j] = (h1[j]>result) ? (j==0 ? -1 : l1[j-1]) : j;
            l0[j] = (h0[j]>result) ? (j==0 ? -1 : l0[j-1]) : j;
            if(j-l1[j]>result) t = 1;
            if(j-l0[j]>result) t = 1;
        }
        result += t;
    }
    printf("%d\n", result);
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.