Hướng dẫn giải của Hình vuông 0 1
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận