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>
#define maxs 10000
#define maxn 110
#define fr(a,b,c) for(a=b;a<=c;a++)
#define frr(a,b,c) for(a=b;a>=c;a--)
using namespace std;
const int dx[]={-1,0,1,0};
      int dy[]={0,1,0,-1};
int n,m,a[maxn][maxn],qx[maxs+10],qy[maxs+10],q,d[maxn][maxn];
int p[maxs+10],px[maxs+10],py[maxs+10],l[maxs+10];
long long re;

void bfs(int x,int y,int val)
{
    int i,j;
    d[x][y]=val; qx[1]=x; qy[1]=y; i=q=1; 
    while (i<=q)
    {
       x=qx[i]; y=qy[i++]; 
       fr(j,0,3)
       {
          int xx=x+dx[j],yy=y+dy[j];
          if (!d[xx][yy] && a[xx][yy]<=val)
          {
              d[xx][yy]=val;
              qx[++q]=xx; qy[q]=yy;           
          }      
       }   
    }
}

int border(int x,int y)
{
    int i;
    fr(i,0,3)
      if (d[x+dx[i]][y+dy[i]]) return 1;
    return 0;
}

int main()
{
    int i,j,x,y;
    scanf("%d%d",&m,&n); 
    fr(i,1,m)
     fr(j,1,n)
     {
        scanf("%d",&a[i][j]); 
        p[a[i][j]]++; 
     }
    fr(i,2,maxs+1) p[i]+=p[i-1];
    fr(i,1,m)
     fr(j,1,n)
     {
         px[p[a[i][j]]]=i; py[p[a[i][j]]--]=j;     
     }
    fr(i,1,m) d[i][0]=d[i][n+1]=-1;
    fr(i,1,n) d[0][i]=d[m+1][i]=-1;
    fr(i,1,m*n)
    {
        x=px[i]; y=py[i];
        if (!d[x][y] && border(x,y)) bfs(x,y,a[x][y]);
    }
    fr(i,2,m-1)
     fr(j,2,n-1)  
      re+=max(0,d[i][j]-a[i][j]);
    cout << re << endl;
    return 0;
}

Code mẫu của happyboy99x

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

const int N = 100, d[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}, INF = 1e9;
int h[N][N], f[N][N], m, n;
pair<int, pair<int, int> > a[N*N];

void enter() {
    cin >> m >> n;
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            cin >> h[i][j], a[i*n+j] = make_pair(h[i][j], make_pair(i, j));
}

void solve() {
    memset(f, -1, sizeof f);
    sort(a, a+m*n);
    for(int i = 0; i < m*n; ++i) {
        int x = a[i].second.first, y = a[i].second.second;
        queue<pair<int, int> > q;
        if(x==0 || x==m-1 || y==0 || y==n-1 || f[x-1][y]!=-1 || f[x+1][y]!=-1 || f[x][y-1]!=-1 || f[x][y+1]!=-1)
            f[x][y] = h[x][y], q.push(make_pair(x, y));
        while(!q.empty()) {
            int x = q.front().first, y = q.front().second; q.pop();
            for(int k = 0; k < 4; ++k) {
                int u = x + d[k][0], v = y + d[k][1];
                if(u >= 0 && u < m && v >= 0 && v < n && h[u][v] <= f[x][y] && f[u][v] == -1)
                    f[u][v] = f[x][y], q.push(make_pair(u, v));
            }
        }
    }
}

void print() {
    int res = 0;
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            res += f[i][j] - h[i][j];
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    solve();
    print();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int N = 1010;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int oo = 1000000009;
using namespace std;
int d[N][N], a[N][N];
int m, n;

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]), d[i][j] = oo;
    priority_queue<iii, vector<iii>, greater<iii> > Q;
    for(int i = 1; i <= m; i++) {
        d[i][1] = a[i][1]; d[i][n] = a[i][n];
        Q.push(iii(a[i][1], ii(i, 1)));
        Q.push(iii(a[i][n], ii(i, n)));
    }
    for(int i = 2; i < n; i++) {
        d[1][i] = a[1][i]; d[m][i] = a[m][i];
        Q.push(iii(a[1][i], ii(1, i)));
        Q.push(iii(a[m][i], ii(m, i)));
    }
    while (!Q.empty()) {
        ii u = Q.top().Y; int du = Q.top().X; Q.pop();
        if (du != d[u.X][u.Y]) continue;
        for(int i = 0; i < 4; i++) {
            ii v (u.X + dx[i], u.Y + dy[i]);
            if (v.X < 1 || v.Y < 1 || v.X > m || v.Y > n) continue;
            if (d[v.X][v.Y] > max(d[u.X][u.Y], a[v.X][v.Y])) {
                d[v.X][v.Y] = max(d[u.X][u.Y], a[v.X][v.Y]);
                Q.push(iii(d[v.X][v.Y], v));
            }
        }
    }
    long long res = 0;
    for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++)
    if (d[i][j] > a[i][j]) res += d[i][j] - a[i][j];
    printf("%lld", res);
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(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 REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

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

const int MN = 1011;
const int MN2 = MN * MN;

int id[MN][MN], h[MN][MN], m, n;
int lab[MN2], height[MN2];
bool out[MN2];
vector< pair<int,int> > ls[MN2];

int getRoot(int u) {
    if (lab[u] < 0) return u;
    return lab[u] = getRoot(lab[u]);
}

void merge(int u, int v) {
    lab[u] = lab[u] + lab[v];
    lab[v] = u;

    height[u] = max(height[u], height[v]);
    out[u] = out[u] | out[v];
}

const int di[] = {-1,1,0,0};
const int dj[] = {0,0,-1,1};

int main() {
    scanf("%d%d", &m, &n);
    int now = 0;
    FOR(i,2,m+1) FOR(j,2,n+1)
        scanf("%d", &h[i][j]);

    m += 2; n += 2;

    FOR(i,1,m) FOR(j,1,n) {
        id[i][j] = ++now;
        lab[now] = -1;
        height[now] = h[i][j];
        if (h[i][j] == 0) out[now] = true;
        else out[now] = false;

        ls[h[i][j]].PB(MP(i,j));
    }

    long long res = 0;

    FOR(t,1,1000000) REP(tt,ls[t].size()) {
        int u = ls[t][tt].F, v = ls[t][tt].S, uu, vv;

        REP(dir,4) {
            uu = u + di[dir], vv = v + dj[dir];
            if (uu < 1 || uu > m || vv < 1 || vv > n) continue;

            int id2 = getRoot(id[uu][vv]);
            int id1 = getRoot(id[u][v]);

            if (height[id1] >= height[id2] && id2 != id1) {
                if (!out[id2]) {
                    res += -lab[id2] * (height[id1] - height[id2]);
                }
                merge(id2, id1);
            }
        }
    }
    cout << res << endl;

    return 0;
}

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   111
int m,n;
int a[MAX][MAX];
int c[MAX][MAX];
int hm,s;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void init(void)
{
    int i,j;
    scanf("%d",&m);
    scanf("%d",&n);
    hm=-1;
    for (i=1;i<=m;i=i+1)
        for (j=1;j<=n;j=j+1)
            {
                scanf("%d",&a[i][j]);
                if (hm<a[i][j]) hm=a[i][j];
            }
    for (i=0;i<=m+1;i=i+1)
        {
            c[i][0]=2;
            c[i][n+1]=2;
        }
    for (i=0;i<=n+1;i=i+1)
        {
            c[0][i]=2;
            c[m+1][i]=2;
        }
    s=0;
}
void dfs(int x,int y)
{
    if (c[x][y]>0) return;
    int i,j;
    c[x][y]=1;
    for (i=0;i<=3;i=i+1)
        if (c[x+dx[i]][y+dy[i]]==0) dfs(x+dx[i],y+dy[i]);
}
void process(void)
{
    int i,j,k;
    for (i=1;i<=hm;i=i+1)
        {
            for (j=1;j<=m;j=j+1)
                for (k=1;k<=n;k=k+1)
                    {
                        if (a[j][k]<i) c[j][k]=0;
                        else c[j][k]=1;
                    }
            for (j=1;j<=m;j=j+1)
                {
                    if (c[j][1]==0) dfs(j,1);
                    if (c[j][n]==0) dfs(j,n);
                }
            for (j=1;j<=n;j=j+1)
                {
                    if (c[1][j]==0) dfs(1,j);
                    if (c[m][j]==0) dfs(m,j);
                }
            for (j=2;j<m;j=j+1)
                for (k=2;k<n;k=k+1)
                    if (c[j][k]==0) s=s+1;
        }
    printf("%d",s);
}
int main(void)
{
    init();
    process();
}

Code mẫu của khuc_tuan

program rain2;
(*****************************************************)
const
      dx:array[1..4] of shortint=(-1,1,0,0);
      dy:array[1..4] of shortint=(0,0,-1,1);
(*****************************************************)
type
    byte = longint ;
    integer = longint ;

    ptype2=^_type2;
    _type2=
           record
                 i,j:byte;
                 next:ptype2;
           end;
    ptype1=^_type1;
    _type1=
           record
                 h:integer;
                 list:ptype2;
           end;
    arr1=array[1..100,1..100] of integer;
    arr2=array[1..10000] of _type1;
    arr3=array[0..101,0..101] of byte;
(*****************************************************)
var
    m,n:integer;
    a:arr1;
    b:arr3;
    queue:record
                a:array[1..30000] of byte;
                l,r:integer;
    end;
    list:^arr2;
    nl:integer;
    sum,count:longint;
{    _t:longint;
    time:longint absolute 0:$46C;}
(*****************************************************)
procedure initqueue;
          begin
               queue.l:=0;
          end;
(*****************************************************)
procedure addQ(i:byte);
          begin
               if queue.l=0 then
                  begin
                       queue.l:=1;
                       queue.r:=1;
                  end
               else if queue.r=30000 then queue.r:=1 else inc(queue.r);
               queue.a[queue.r]:=i;
          end;
(*****************************************************)
function delete:byte;
         begin
              delete:=queue.a[queue.l];
              if queue.l=queue.r then queue.l:=0
              else if queue.l=30000 then queue.l:=1 else inc(queue.l);
         end;
(*****************************************************)
function empty:boolean;
         begin
              empty:=queue.l=0;
         end;
(*****************************************************)
procedure main(var list:arr2);
(*****************************************************)
procedure init;
          begin
               fillchar(a, sizeof(a), 0);
               fillchar(b, sizeof(b), 0);
               fillchar( queue, sizeof(queue), 0);
               nl := 0;
               sum := 0;
               count := 0;
               fillchar(list,sizeof(list),0);
          end;
(*****************************************************)
procedure nhap;
          var i,j:integer;
          begin
               readln(m,n);
               for i:=1 to m do
                   begin
                        for j:=1 to n do read(a[i,j]);
                        readln;
                   end;
          end;
(*****************************************************)
procedure add(var l:ptype2;i,j:byte);
          var p:ptype2;
          begin
               new(p);
               p^.i:=i;
               p^.j:=j;
               p^.next:=l;
               l:=p;
          end;
(*****************************************************)
procedure createlist;
          var i,j:byte;
              l,r,mid:integer;
          begin
               nl:=0;
               for i:=1 to m do
                   for j:=1 to n do
                       begin
                            if (nl=0) or (list[nl].h<a[i,j]) then
                               begin
                                    inc(nl);
                                    list[nl].h:=a[i,j];
                                    add(list[nl].list,i,j);
                                    continue;
                               end;
                            l:=1;
                            r:=nl;
                            while l<>r do
                                  begin
                                       mid:=(l+r) div 2;
                                       if list[mid].h=a[i,j] then
                                          begin
                                               l:=mid;
                                               r:=mid;
                                               break;
                                          end;
                                       if list[mid].h>a[i,j] then r:=mid else l:=mid+1;
                                  end;
                            if list[l].h=a[i,j] then add(list[l].list,i,j)
                            else
                                begin
                                     inc(nl);
                                     move(list[l],list[l+1],(nl-l)*sizeof(_type1));
                                     list[l].h:=a[i,j];
                                     list[l].list:=nil;
                                     add(list[l].list,i,j);
                                end;
                       end;
          end;
(*****************************************************)
procedure loang(i,j:byte);
          var k:byte;
          begin
               initqueue;
               for k:=1 to 4 do if b[i+dx[k],j+dy[k]]=2 then
                   begin
                        addQ(i+dx[k]);
                        addQ(j+dy[k]);
                        dec(count);
                        b[i+dx[k],j+dy[k]]:=0;
                   end;
               while not empty do
                     begin
                          i:=delete;
                          j:=delete;
                          for k:=1 to 4 do if b[i+dx[k],j+dy[k]]=2 then
                              begin
                                   addQ(i+dx[k]);
                                   addQ(j+dy[k]);
                                   dec(count);
                                   b[i+dx[k],j+dy[k]]:=0;
                              end;
                     end;
          end;
(*****************************************************)
procedure cat(x:integer);
          var p:ptype2;
              i,j,k:byte;
          begin
               p:=list[x].list;
               while p<>nil do
                     begin
                          i:=p^.i;
                          j:=p^.j;
                          for k:=1 to 4 do if b[i+dx[k],j+dy[k]]=0 then b[i,j]:=0;
                          if b[i,j]=0 then loang(i,j)
                          else
                              begin
                                   b[i,j]:=2;
                                   inc(count);
                              end;
                          p:=p^.next;
                     end;
               sum:=sum+(list[x+1].h-list[x].h)*count;
          end;
(*****************************************************)
procedure xuly;
          var i,j:integer;
          begin
               createlist;
               for i:=1 to m do
                   for j:=1 to n do b[i,j]:=1;
               for i:=1 to nl-1 do
                   begin
                        cat(i);
                   end;
          end;
(*****************************************************)
procedure ghi;
          begin
               writeln( sum);
          end;
(*****************************************************)
begin
     init;
     nhap;
     xuly;
     ghi;
end;
(*****************************************************)
procedure mktest;
          var i,j:integer;
              k:integer;
          begin
               randomize;
               m:=100;
               n:=100;
               k:=0;
               writeln(m,' ',n);
               for i:=1 to m do
                   begin
                        for j:=1 to n do
                            begin
                                 inc(k);
                                 write(k,' ');
                            end;
                        writeln;
                   end;
          end;
(*****************************************************)
var
 i,t : integer ;
begin
{     mktest;
     _t:=time;}
     //readln( t);
     //for i:=1 to t do
     // begin
       new(list);
       main(list^);
       dispose(list);
     // end;
{     writeln('Thoi gian:',(time-_t)/18.23 :0:4);}
end.