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

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

int main()
{
    int m,n,f[2][5050]={0};
    long long ans=0;
    char s[5050];

    cin >> m >> n;

    int z=0;
    for (int i=0;i<m;i++,z^=1)
    {
        scanf("%s",s);
        for (int j=0;j<n;j++)
            if (s[j]=='1') f[z][j]=0;
            else 
            {
                f[z][j]=min(f[z][j-1],min(f[z^1][j],f[z^1][j-1]))+1;
                ans+=f[z][j];
            }
    }

    cout << ans << endl;
}

Code mẫu của happyboy99x

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

const int N = 5000 + 5;
char s[N][N];
int f[N][N], m, n;

int main() {
    scanf("%d%d",&m,&n);
    for(int i = 1; i <= m; ++i) scanf("%s", s[i] + 1);
    long long res = 0;
    for(int i = 1; i <= m; ++i)
    for(int j = 1; j <= n; ++j) if(s[i][j] == 0x30) {
        f[i][j] = 1;
        if(0x30 == s[i-1][j] && 0x30 == s[i-1][j-1] && 0x30 == s[i][j-1])
            f[i][j] = 1 + min(f[i-1][j], min(f[i-1][j-1], f[i][j-1]));
        res += f[i][j];
    }
    cout << res << "\n";
    return 0;
}

Code mẫu của ladpro98

program nkcnt1;//dp;
uses    math;
const   maxn=5005;
        fi='';
var     a:array[1..maxn] of ansistring;
        f:array[0..maxn,0..maxn] of longint;
        m,n:longint;
        res:int64;

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

procedure dp;
var     i,j:longint;
begin
        for i:=1 to n do
        if a[1][i]='0' then
        begin
                f[1,i]:=1;
                inc(res);
        end;
        for i:=2 to m do
        if a[i][1]='0' then
        begin
                f[i,1]:=1;
                inc(res);
        end;
        for i:=2 to m do
        for j:=2 to n do
        if (a[i][j]='0') then
        begin
                if (a[i-1][j]='0') and (a[i][j-1]='0') and (a[i-1][j-1]='0') then
                f[i,j]:=min(min(f[i-1,j],f[i,j-1]),f[i-1,j-1])+1
                else
                f[i,j]:=1;
                inc(res,f[i,j]);
        end;
end;

begin
        input;
        dp;
        write(res);
end.

Code mẫu của RR

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

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);

int m, n;
char a[5011];
int row[5011], past[5011];

int main() {
    scanf("%d%d\n", &m, &n);
    long long res = 0;
    for(int i = 1; i <= m; ++i) {
        gets(a);
        int k = 1;
        for(int j = 1; j <= n; ++j) {
            --k; if (k < 0) k = 0;
            while (j+k <= n && a[j+k-1] == '0' && past[j] >= k && past[j+1] >= k)
                ++k;
            past[j] = k;
            res += k;
        }
    }
    std::cout << res << std::endl;
    return 0;
}