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

const fi='';
      fo='';
      maxn=1515;
      dx:array[1..4] of longint=(-1,0,1,0);
      dy:array[1..4] of longint=(0,1,0,-1);
      r:array[1..4] of longint=(3,4,1,2);
var n,m,re,sm,s,f,num:longint;
    sl:array[0..1] of longint;
    a:array[0..maxn,0..maxn] of char;
    d:array[0..maxn,0..maxn] of longint;
    q:array[1..maxn*maxn,0..1] of longint;
    lab,deg:array[1..maxn*maxn shr 1] of longint;
    next:array[0..1,1..maxn*maxn shr 1,0..1] of longint;
    dau:array[0..maxn,0..maxn,1..4] of boolean;

procedure rf;
var i,j:longint;
begin
     assign(input,fi); reset(input);
     readln(m,n);
     for i:=1 to m do 
     begin
          for j:=1 to n do read(a[i,j]); 
          readln;
          dau[i,1,4]:=true; dau[i,n,2]:=true;
     end;
     for i:=1 to n do
     begin
          dau[1,i,1]:=true; dau[m,i,3]:=true;
     end;
     close(input);
end;

procedure bfs(x,y:longint);
var i,j:longint;
begin
     num:=1; i:=1;
     q[1,0]:=x; q[1,1]:=y;
     inc(sm); d[x,y]:=sm;
     lab[sm]:=sm;
     if a[x,y]='L' then
     begin
          if s=0 then s:=sm
          else f:=sm;
     end;
     repeat
           for j:=1 to 4 do
           if not dau[q[i,0],q[i,1],j] then
           begin
                x:=q[i,0]+dx[j]; y:=q[i,1]+dy[j];
                if d[x,y]=0 then
                begin
                     dau[x,y,r[j]]:=true;
                     if a[x,y]='X' then
                     begin
                          inc(sl[0]);
                          next[0,sl[0],0]:=x; next[0,sl[0],1]:=y;
                          d[x,y]:=sm;
                     end
                     else
                     begin
                          inc(num);
                          q[num,0]:=x; q[num,1]:=y;
                          d[x,y]:=sm;
                          if a[x,y]='L' then
                          begin
                               if s=0 then s:=sm
                               else f:=sm;
                          end;
                     end;
                end;
           end;
           inc(i);
     until i>num;
end;

function find(x:longint):longint;
begin
     if x=lab[x] then find:=x
     else
     begin
          lab[x]:=find(lab[x]);
          find:=lab[x];
     end;
end;

procedure union(x,y:longint);
var u,v:longint;
begin
     u:=find(x); v:=find(y);
     if deg[u]>deg[v] then lab[v]:=u
     else
     begin
          if deg[u]<deg[v] then lab[u]:=v
          else
          begin
               if u<>v then
           begin
            lab[v]:=u;
            inc(deg[u]);
           end;
          end;
     end;
end;

procedure melt(cur:longint);
var i,j,x,y,t,u:longint;
begin
     sl[1-cur]:=0;
     for i:=1 to sl[cur] do
     begin
          a[next[cur,i,0],next[cur,i,1]]:='.';
          for j:=1 to 4 do
          if not dau[next[cur,i,0],next[cur,i,1],j] then
          begin
               x:=next[cur,i,0]+dx[j]; y:=next[cur,i,1]+dy[j];
               if a[x,y]='X' then
               begin
                    if d[x,y]=0 then
                    begin
                         inc(sl[1-cur]);
                         next[1-cur,sl[1-cur],0]:=x;
                         next[1-cur,sl[1-cur],1]:=y;
                         d[x,y]:=d[next[cur,i,0],next[cur,i,1]];
                         dau[x,y,r[j]]:=true;
                    end;
               end
               else union(d[x,y],d[next[cur,i,0],next[cur,i,1]]);
          end;
     end;
end;

procedure pr;
var i,j:longint;
begin
     sm:=0; s:=0; f:=0; sl[0]:=0;
     for i:=1 to m do
         for j:=1 to n do
             if (d[i,j]=0) and (a[i,j]<>'X') then
                bfs(i,j);
     re:=0;
     if (s=f) and (s>0) then exit;
     repeat
           inc(re);
           melt(1-re and 1);
     until find(s)=find(f);
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     writeln(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<bits/stdc++.h>
using namespace std;

const int N = 1500, d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int f[N][N], m, n;
char s[N][N+1];
bool vst[N][N];

bool valid(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }

void enter() {
    cin >> m >> n;
    for(int i = 0; i < m; ++i)
        cin >> s[i];
    for(int i = 0, c = '0'; i < m; ++i)
        for(int j = 0; j < n; ++j)
            if(s[i][j] == 'L') s[i][j] = c++;
}

void precal() {
    memset(f, -1, sizeof f);
    queue<pair<int, int> > q;
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            if(s[i][j] != 'X') f[i][j] = 0, q.push(make_pair(i, j));
    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(valid(u, v) && f[u][v] == -1)
                f[u][v] = f[x][y] + 1, q.push(make_pair(u, v));
        }
    }
}

int solve() {
    queue<pair<int, int> > q1, q2;
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j)
            if(s[i][j] == '0')
                q1.push(make_pair(i, j)), vst[i][j] = true;
    for(int step = 0; !q1.empty(); ++step) {
        while(!q1.empty()) {
            int x = q1.front().first, y = q1.front().second; q1.pop();
            q2.push(make_pair(x, y));
            for(int k = 0; k < 4; ++k) {
                int u = x + d[k][0], v = y + d[k][1];
                if(valid(u, v) && !vst[u][v] && f[u][v] <= step)
                    vst[u][v] = true, q1.push(make_pair(u, v));
            }
        }
        while(!q2.empty()) {
            int x = q2.front().first, y = q2.front().second; q2.pop();
            if(s[x][y] == '1') return step;
            for(int k = 0; k < 4; ++k) {
                int u = x + d[k][0], v = y + d[k][1];
                if(valid(u, v) && !vst[u][v] && f[u][v] <= step + 1)
                    vst[u][v] = true, q1.push(make_pair(u, v));
            }
        }
    }
    assert(false);
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    precal();
    cout << solve();
    return 0;
}

Code mẫu của ladpro98

program labudovi;
uses    math;
type    e=record
        x,y:longint;
        end;
const   maxn=2000;
        fi='';
        dx:array[1..4] of longint = (1,-1,0,0);
        dy:array[1..4] of longint = (0,0,1,-1);
var     m,n,t,lW,rW,rF,lF,day,i,j:longint;
        ice,check,visit:array[1..maxn,1..maxn] of boolean;
        s:array[1..2] of e;
        q,q2,st:array[1..maxn*maxn] of e;

procedure input;
var     inp:text;
        i,j:longint;
        ss:ansistring;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,m,n);
        for i:=1 to m do
        begin
                readln(inp,ss);
                for j:=1 to n do
                if ss[j]='X' then
                        ice[i,j]:=true
                else
                if ss[j]='L' then
                begin
                        inc(t);
                        s[t].x:=i;
                        s[t].y:=j;
                        inc(rW);
                        q[rW].x:=i;
                        q[rW].y:=j;
                        check[i,j]:=true;
                end
                else
                begin
                        inc(rW);
                        q[rW].x:=i;
                        q[rW].y:=j;
                        check[i,j]:=true;
                end;
        end;
        close(inp);
end;

function outBound(i,j:longint):boolean;
begin
        exit(not ((1<=i) and (i<=m) and (1<=j) and (j<=n)));
end;

procedure bfsWater;
var     i,j,x,y:longint;
        u:e;
begin
        j:=0;
        while lW<=rW do
        begin
                u:=q[lW];inc(lW);
                for i:=1 to 4 do
                begin
                        x:=u.x+dx[i];
                        y:=u.y+dy[i];
                        if outBound(x,y) then continue;
                        if not check[x,y] then
                        begin
                                if ice[x,y] then
                                begin
                                        ice[x,y]:=false;
                                        check[x,y]:=true;
                                        inc(j);
                                        st[j].x:=x;
                                        st[j].y:=y;
                                end
                                else
                                begin
                                        check[x,y]:=true;
                                        inc(rW);
                                        q[rW].x:=x;
                                        q[rW].y:=y;
                                end;
                        end;
                end;
        end;
        for i:=1 to j do
        begin
                inc(rW);
                q[rW]:=st[i];
        end;
end;

procedure bfsFind;
var     i,j,x,y:longint;
        u:e;
        keep:boolean;
begin
        j:=0;
        while lF<=rF do
        begin
                u:=q2[lF];inc(lF);
                keep:=false;
                for i:=1 to 4 do
                begin
                        x:=u.x+dx[i];
                        y:=u.y+dy[i];
                        if outBound(x,y) then continue;
                        if ice[x,y] then keep:=true
                        else
                        if not visit[x,y] then
                        begin
                                visit[x,y]:=true;
                                inc(rF);
                                q2[rF].x:=x;
                                q2[rF].y:=y;
                                if (q2[rF].x=s[2].x) and (q2[rF].y=s[2].y) then
                                begin
                                        write(day);
                                        halt;
                                end;
                        end;
                end;
                if keep then
                begin
                        inc(j);
                        st[j]:=u;
                end;

        end;
        for i:=1 to j do
        begin
                inc(rF);
                q2[rF]:=st[i];
        end;
end;

begin
        input;
        lF:=1;rF:=1;lW:=1;
        q2[1]:=s[1];visit[s[1].x,s[1].y]:=true;
        while (lW<=rW) and (lF<=rF) do
        begin
                bfsFind;
                {for i:=1 to m do
                begin
                        for j:=1 to n do
                        if ice[i,j] then write('X')
                        else write('.');
                        writeln;
                end;   }
                inc(day);
                bfsWater;
                //readln;
        end;
end.

Code mẫu của RR

{$IFDEF RR}
  {$R+,Q+}
  {$inline off}
  {$Mode objFPC}
{$ELSE}
  {$R-,Q-}
  {$inline on}
{$ENDIF}

uses math;
const
  FINP          =       {$IFDEF RR} 'input.txt';  {$ELSE} ''; {$ENDIF}
  FOUT          =       {$IFDEF RR} 'output.txt'; {$ELSE} ''; {$ENDIF}
  MAXN          =       1511;
  di            :       array[1..4] of longint=(-1,1,0,0);
  dj            :       array[1..4] of longint=(0,0,-1,1);
type
  Tqueue        =       object
        u,v     :       array[1..MAXN*MAXN] of longint;
        first   :       longint;
        last    :       longint;
        procedure push(uu,vv:longint);
        procedure pop(var uu,vv:longint);
  end;

var
  f1,f2         :       text;
  queue         :       Tqueue;
  melted        :       array[1..MAXN,1..MAXN] of longint;
  a             :       array[1..MAXN,1..MAXN] of char;
  visited       :       array[1..MAXN,1..MAXN] of boolean;
  m,n           :       longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i,j:longint;
    begin
      readln(f1,m,n);
      for i:=1 to m do
        begin
          for j:=1 to n do read(f1,a[i,j]);
          readln(f1);
        end;
    end;
procedure Tqueue.push(uu,vv:longint); inline;
    begin
      inc(last);
      u[last]:=uu;
      v[last]:=vv;
    end;
procedure Tqueue.pop(var uu,vv:longint); inline;
    begin
      uu:=u[first];
      vv:=v[first];
      inc(first);
    end;
procedure init;
    var
      u,v,uu,vv,dir:longint;
    begin
      fillchar(melted,sizeof(melted),255);
      queue.first:=1; queue.last:=0;
      for u:=1 to m do
      for v:=1 to n do
        if a[u,v]<>'X' then
          begin
            melted[u,v]:=0;
            queue.push(u,v);
          end;
      while queue.first<=queue.last do
        begin
          queue.pop(u,v);
          for dir:=1 to 4 do
            begin
              uu:=u+di[dir]; vv:=v+dj[dir];
              if (uu>0) and (vv>0) and (uu<=m) and (vv<=n) and (melted[uu,vv]=-1) then
                begin
                  melted[uu,vv]:=melted[u,v]+1;
                  queue.push(uu,vv);
                end;
            end; //for dir
        end; //while queue.first<=queue.last
    end;
procedure solve;
    var
      xyz,time,save,u,v,uu,vv,dir,startu,startv,targetu,targetv:longint;
    begin
      time:=0; startu:=0;
      for u:=1 to m do
      for v:=1 to n do
        if a[u,v]='L' then
          if startu=0 then begin startu:=u; startv:=v; end
          else begin targetu:=u; targetv:=v; end;
      fillchar(visited,sizeof(visited),false);
      queue.first:=1; queue.last:=0;
      queue.push(startu,startv);
      visited[startu,startv]:=true;
      repeat
        save:=queue.last;
        while queue.first<=queue.last do
          begin
            queue.pop(u,v);
            for dir:=1 to 4 do
              begin
                uu:=u+di[dir]; vv:=v+dj[dir];
                if (uu>0) and (uu<=m) and (vv>0) and (vv<=n) then
                  if (melted[uu,vv]<=time) and (not visited[uu,vv]) then
                    begin
                      visited[uu,vv]:=true;
                      queue.push(uu,vv);
                      if (uu=targetu) and (vv=targetv) then
                        begin
                          writeln(f2,time);
                          exit;
                        end;
                    end;
              end; //for dir
          end; //while queue.first<=queue.last
        queue.first:=save;
        inc(time);
      until false;
    end;

begin
  openF;
  inp;
  init;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(typeof(n) i = 0; i < (n); ++i)
#define Repd(i,n) for(typeof(n) i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(typeof(b) i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(typeof(a) i = (a); i >= (b); --i)
#define Fit(i,v) for(typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define Fitd(i,v) for(typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define nl puts("")
#define sp printf(" ")
#define ok puts("ok")
//#include <conio.h>

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} };
template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }
const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

const double PI = 2 * acos(0);
const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const double eps = 1e-9;
const ll mod = 100000007;
typedef pair<int, int> II;

#define maxn 1505
#define maxe 100005

int n, m, rs = -1, cs, rf, cf;
string s[maxn];
char ch[maxn];
int f[maxn][maxn] = {0};
bool flag[maxn][maxn] = {0};
II que[maxn * maxn], q[maxn * maxn], temp[maxn * maxn];

bool thoaman(int r, int c){
    return (r >= 0 && r < n && c >= 0 && c < m);
}

int go(){

    int size1 = 0, r, c, rr, cc, size, sq, sq1;
    Rep(i, n) Rep(j, m) if(s[i][j] == '.' || s[i][j] == 'L'){
        f[i][j] = 1;
        que[size1++] = mp(i, j);
    }

    sq1 = 0; q[sq1++] = mp(rs, cs);

    for(int x = 0;; x++){
   // cout << x << endl;
    sq = sq1;
    sq1 = 0;
    Rep(i, sq){
        r = q[i].fi; c = q[i].se;
        if(r == rf && c == cf) return x;
        Rep(t, 4){
            rr = r + dr[t]; cc = c + dc[t];
            if(thoaman(rr, cc) && f[rr][cc] > 0 && !flag[rr][cc]){
                flag[rr][cc] = 1;
                temp[sq1++] = mp(rr, cc);
                q[sq++] = mp(rr, cc);
            }
        }
    }
    Rep(i, sq1) q[i] = temp[i];
    if(x == 0) q[sq1++] = mp(rs, cs);
   // Rep(i, sq1) printf("%d %d   ", q[i].fi, q[i].se); puts("");

    size = size1;
    size1 = 0;        
    Rep(i, size){
        r = que[i].fi; c = que[i].se;
        if(f[r][c] == x + 2) break;
        Rep(t, 4){
            rr = r + dr[t]; cc = c + dc[t];
            if(thoaman(rr, cc) && s[rr][cc] == 'X' && f[rr][cc] <= 0){
                f[rr][cc] = f[r][c] + 1;
                temp[size1++] = mp(rr, cc);
            }
        }
    }
    Rep(i, size1) que[i] = temp[i];
    //Rep(i, size1) printf("%d %d   ", que[i].fi, que[i].se); puts("");


    //if(x < 2000) cout << x << " " << size << endl;

    }

}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    gi(n); gi(m);
    Rep(i, n){
        gs(ch); s[i] = ch;
        Rep(j, m) if(s[i][j] == 'L'){
            if(rs == -1){
                rs = i; cs = j;
            }
            else{
                rf = i; cf = j;
            }
        }
    }
    //cout << clock() << endl;
    cout << go() << endl;;
    //cout << clock();
    return 0;
}

Code mẫu của ll931110

{$inline on}
{$MODE DELPHI}
program LABUDOVI;
const
  input  = '';
  output = '';
  maxn = 1500;
  dx: array[1..4] of integer = (-1,0,1,0);
  dy: array[1..4] of integer = (0,1,0,-1);
type
  rec = record
    x,y: integer;
  end;
var
  a: array[1..maxn,1..maxn] of char;
  free: array[0..maxn + 1,0..maxn + 1] of boolean;
  rank: array[1..maxn,1..maxn] of integer;
  queue: array[1..maxn * maxn] of rec;
  p: array[1..maxn,1..maxn] of rec;
  n,m,res,front,rear,qrear: longint;
  s,t,zero,st: rec;

function comp(r1,r2: rec): boolean;inline;
begin
  comp := (r1.x = r2.x) and (r1.y = r2.y);
end;

procedure init;inline;
var
  f: text;
  i,j: integer;
begin
  assign(f, input);
    reset(f);

  fillchar(free, sizeof(free), true);

  readln(f, m, n);
  for i := 1 to n do
    begin
      free[0,i] := false;
      free[m + 1,i] := false;
    end;

  for i := 1 to m do
    begin
      free[i,0] := false;
      free[i,n + 1] := false;
    end;

  zero.x := 0;
  zero.y := 0;

  s := zero;
  t := zero;

  for i := 1 to m do
    begin
      for j := 1 to n do
        begin
          read(f, a[i,j]);
          if a[i,j] = 'L' then
            begin
              if comp(s,zero) then
                begin
                  s.x := i;
                  s.y := j;
                end
              else
                begin
                  t.x := i;
                  t.y := j;
                end;
              a[i,j] := '.';
            end;
        end;
      readln(f);
    end;

  close(f);
end;

procedure push(u,v: integer);inline;
begin
  inc(rear);
  queue[rear].x := u;
  queue[rear].y := v;
end;

function pop: rec;
begin
  pop := queue[front];
  inc(front);
end;

procedure DFS(i,j: integer);inline;
var
  k,kx,ky: integer;
begin
  p[i,j] := st;
  free[i,j] := false;

  for k := 1 to 4 do
    begin
      kx := i + dx[k];
      ky := j + dy[k];
      if free[kx,ky] then
        begin
          free[kx,ky] := false;
          if a[kx,ky] = '.' then DFS(kx,ky) else push(kx,ky);
        end;
    end;
end;

function root(u: rec): rec;inline;
begin
  if not comp(u,p[u.x,u.y]) then p[u.x,u.y] := root(p[u.x,u.y]);
  root := p[u.x,u.y];
end;

procedure union(r1,r2: rec);inline;
var
  r3,r4: rec;
begin
  r3 := root(r1);
  r4 := root(r2);
  if rank[r3.x,r3.y] > rank[r4.x,r4.y]
    then p[r4.x,r4.y] := r3 else p[r3.x,r3.y] := r4;

  if rank[r3.x,r3.y] = rank[r4.x,r4.y] then inc(rank[r4.x,r4.y]);
end;

function valid(r: rec): boolean;inline;
begin
  valid := (0 < r.x) and (r.x <= m) and (0 < r.y) and (r.y <= n);
end;

procedure update(u: rec);inline;
var
  k: integer;
  tmp,ts,pts: rec;
begin
  free[u.x,u.y] := false;
  tmp := zero;

  for k := 1 to 4 do
    begin
      ts.x := u.x + dx[k];
      ts.y := u.y + dy[k];

      if valid(ts) then
        begin
          pts := p[ts.x,ts.y];

          if free[ts.x,ts.y] then
            begin
              push(ts.x,ts.y);
              free[ts.x,ts.y] := false;
            end
          else
            if comp(tmp,zero) then
              begin
                tmp := pts;
                p[u.x,u.y] := ts;
              end
          else if not comp(pts,zero) then union(tmp,pts);
        end;
    end;
end;

procedure solve;inline;
var
  i,j: integer;
  u: rec;
begin
  front := 1;
  rear := 0;
  fillchar(rank, sizeof(rank), 0);

  for i := 1 to m do
    for j := 1 to n do
      if free[i,j] and (a[i,j] = '.') then
        begin
          st.x := i;
          st.y := j;
          DFS(i,j);
        end;

  res := 0;
  while not comp(root(p[s.x,s.y]),root(p[t.x,t.y])) do
    begin
      inc(res);
      qrear := rear;

      while front <= qrear do
        begin
          u := pop;
          update(u);
        end;
    end;
end;

procedure printresult;inline;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAX   1515
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
class DisjointSet {
    private:
    vector<int> lab;
    int find(int x) {
        if (lab[x]<0) return (x);
        lab[x]=find(lab[x]);
        return (lab[x]);
    }
    public:
    DisjointSet(){}
    DisjointSet(int n) {
        lab.assign(n+7,-1);
    }
    bool sameSet(int u,int v) {
        return (find(u)==find(v));
    }
    bool join(int a,int b) {
        int x=find(a);
        int y=find(b);
        if (x==y) return (false);
        if (lab[x]>lab[y]) swap(x,y);
        lab[x]+=lab[y];
        lab[y]=x;
        return (true);
    }
};
char a[MAX][MAX];
int dis[MAX][MAX];
pair<int,int> sortDis[MAX*MAX],swan[7];
int m,n;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void init(void) {
    scanf("%d%d",&m,&n);
    FOR(i,1,m) scanf("%s",a[i]+1);
    int nSwan=0;
    FOR(i,1,m) FOR(j,1,n) if (a[i][j]=='L') swan[++nSwan]=make_pair(i,j);
}
bool inside(int x,int y) {
    if (x<1 || x>m || y<1 || y>n) return (false);
    return (true);
}
void bfs(void) {
    memset(dis,-1,sizeof dis);
    queue<pair<int,int> > q;
    FOR(i,1,m) FOR(j,1,n) if (a[i][j]!='X') {
        dis[i][j]=0;
        q.push(make_pair(i,j));
    }
    int nVst=0;
    while (!q.empty()) {
        int ux=q.front().fi;
        int uy=q.front().se;
        q.pop();
        sortDis[++nVst]=make_pair(ux,uy);
        REP(i,4) if (inside(ux+dx[i],uy+dy[i])) {
            int vx=ux+dx[i];
            int vy=uy+dy[i];
            if (dis[vx][vy]<0) {
                dis[vx][vy]=dis[ux][uy]+1;
                q.push(make_pair(vx,vy));
            }
        }
    }
}
int cellID(int x,int y) {
    return ((x-1)*n+y);
}
void process(void) {
    DisjointSet dsu(m*n);
    int j=1;
    int sta=cellID(swan[1].fi,swan[1].se);
    int fin=cellID(swan[2].fi,swan[2].se);
    REP(i,MAX*MAX) {
        while (j<=m*n && dis[sortDis[j].fi][sortDis[j].se]<=i) {
            int x=sortDis[j].fi;
            int y=sortDis[j].se;
            REP(k,4) if (inside(x+dx[k],y+dy[k]) && dis[x+dx[k]][y+dy[k]]<=i)
                dsu.join(cellID(x,y),cellID(x+dx[k],y+dy[k]));
            j++;
        }
        if (dsu.sameSet(sta,fin)) {
            printf("%d\n",i);
            return;
        }
    }
}
int main(void) {
#ifndef ONLINE_JUDGE
    freopen("tmp.txt","r",stdin);
#endif // ONLINE_JUDGE
    init();
    bfs();
    process();
    return 0;
}