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 maxn=501;
      dx:array[1..4] of longint=(-1,0,1,0);
      dy:array[1..4] of longint=(0,1,0,-1);
var n,m,re,num,i,j,x,y,sx,sy,fx,fy,t:longint;
    a:array[1..maxn,1..maxn] of char;
    b,d:array[1..maxn,1..maxn] of longint;
    q:array[1..maxn*maxn,0..1] of longint;

function check(x,y:longint):boolean;
begin
     check:=(x>0) and (y>0) and (x<=m) and (y<=n);
end;

begin
     readln(m,n);
     num:=0;
     for i:=1 to m do
     begin
          for j:=1 to n do
          begin
               read(a[i,j]);
               b[i,j]:=-1;
               if a[i,j]='+' then
               begin
                    inc(num);
                    q[num,0]:=i; q[num,1]:=j;
                    b[i,j]:=0;
               end;
               if a[i,j]='V' then
               begin
                    sx:=i; sy:=j;
               end;
               if a[i,j]='J' then
               begin
                    fx:=i; fy:=j;
               end;
          end;
          readln;
     end;
     i:=1;
     repeat
           for j:=1 to 4 do
           begin
                x:=q[i,0]+dx[j]; y:=q[i,1]+dy[j];
                if check(x,y) and (b[x,y]=-1) then
                begin
                     inc(num);
                     q[num,0]:=x; q[num,1]:=y;
                     b[x,y]:=b[q[i,0],q[i,1]]+1;
                end;
           end;
           inc(i);
     until (i>num) or (num=m*n);
     if b[sx,sy]<b[fx,fy] then t:=b[sx,sy] else t:=b[fx,fy];
     q[1,0]:=sx; q[1,1]:=sy;
     for re:=t downto 0 do
     begin
          if t=0 then break;
          fillchar(d,sizeof(d),0);
          num:=1; d[sx,sy]:=1; i:=1;
          repeat
                for j:=1 to 4 do
                begin
                     x:=q[i,0]+dx[j]; y:=q[i,1]+dy[j];
                     if check(x,y) and (d[x,y]=0) and (b[x,y]>=re) then
                     begin
                          inc(num);
                          q[num,0]:=x; q[num,1]:=y;
                          d[x,y]:=1;
                          if d[fx,fy]<>0 then break;
                     end;
                end;
                inc(i);
          until (i>num) or (d[fx,fy]<>0);
          if d[fx,fy]<>0 then break;
     end;
     writeln(re);
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long LL;

#define sz(a) (int((a).size()))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 505

char a[N][N];
int f[N][N], d[N][N], m, n;
int delta[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
bool vst[N][N];
ii v;

void enter() {
    scanf("%d%d",&m,&n);
    rep(i,m) scanf("%s",a[i]);
}

void bfs() {
    queue<ii> qu; 
    rep(i,m) rep(j,n) if(a[i][j] == '+'){
        qu.push(ii(i,j)); vst[i][j] = 1;
    } else if(a[i][j] == 'V') v = ii(i,j);
    for(int dis = 0; !qu.empty(); ++dis) rep(Z, qu.size()) {
        int x = qu.front().fi, y = qu.front().se; qu.pop();
        d[x][y] = dis;
        rep(k,4) {
            int i = x + delta[k][0], j = y + delta[k][1];
            if(i>=0&&i<m&&j>=0&&j<n&&!vst[i][j]) {
                vst[i][j]=1;
                qu.push(ii(i,j));
            }
        }
    }
}

class cmp {
    bool rev;
    public:
    cmp(const bool& rev_=false){rev = rev_;}
    bool operator() (const ii&a, const ii&b) const {
        return d[a.fi][a.se] < d[b.fi][b.se];
    }
};

void solve() {
    priority_queue<ii,vii,cmp> qu;
    qu.push(v); memset(f, -1, sizeof f); f[v.fi][v.se] = d[v.fi][v.se];
    while(!qu.empty()) {
        int x = qu.top().fi, y = qu.top().se; qu.pop();
        rep(k,4) {
            int i = x + delta[k][0], j = y + delta[k][1];
            if(i>=0&&i<m&&j>=0&&j<n&&f[i][j]==-1) {
                f[i][j] = min(f[x][y], d[i][j]);
                if(a[i][j] == 'J') {
                    printf("%d\n", f[i][j]);
                    return;
                }
                qu.push(ii(i,j));
            }
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
#endif
    enter();
    bfs();
    //rep(i,m) { rep(j,n) printf("%d ", d[i][j]); putchar(10); }
    solve();
    return 0;
}

Code mẫu của ladpro98

program vukvn;
uses    math;
type    e=record
        x,y:longint;
        end;
const   tree = 1;
        free = 0;
        maxn=555;
        fi='';
        dx:array[1..4] of longint = (0,0,1,-1);
        dy:array[1..4] of longint = (1,-1,0,0);
var     a:array[1..maxn,1..maxn] of longint;

        avail:array[1..maxn,1..maxn] of boolean;
        q:array[1..maxn*maxn] of e;
        dis:array[1..maxn,1..maxn] of longint;
        l,r,m,n,res:longint;
        st,fn:e;

procedure input;
var     inp:text;
        i,j:longint;
        s:ansistring;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,m);
        for i:=1 to n do
        for j:=1 to m do
        avail[i,j]:=true;
        for i:=1 to n do
        begin
                readln(inp,s);
                for j:=1 to m do
                if s[j]='+' then
                begin
                        a[i,j]:=tree;
                        avail[i,j]:=false;
                        inc(r);
                        q[r].x:=i;
                        q[r].y:=j;
                end
                else
                begin
                        a[i,j]:=free;
                        if s[j]='V' then
                        begin
                                st.x:=i;
                                st.y:=j;
                        end;
                        if s[j]='J' then
                        begin
                                fn.x:=i;
                                fn.y:=j;
                        end;
                end;
        end;
        close(inp);
end;

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

procedure bfsDis;
var     u:e;
        i,x,y:longint;

begin
        l:=1;
        while l<=r do
        begin
                u:=q[l];inc(l);
                for i:=1 to 4 do
                begin
                        x:=u.x+dx[i];
                        y:=u.y+dy[i];
                        if inBound(x,y) and (avail[x,y]) then
                        begin
                                avail[x,y]:=false;
                                inc(r);
                                q[r].x:=x;
                                q[r].y:=y;
                                dis[x,y]:=dis[u.x,u.y]+1;
                        end;
                end;
        end;
end;

function bfsFind(lim:longint):boolean;
var     i,j,x,y:longint;
        u:e;
begin
        l:=1;r:=1;
        q[1]:=st;
        for i:=1 to n do
        for j:=1 to m do
        avail[i,j]:=true;
        avail[st.x,st.y]:=false;
        while l<=r do
        begin
                u:=q[l];inc(l);
                for i:=1 to 4 do
                begin
                        x:=u.x+dx[i];
                        y:=u.y+dy[i];
                        if inBound(x,y) and (avail[x,y]) and (a[x,y]=free) and (dis[x,y]>=lim)
                        then
                        begin
                                avail[x,y]:=false;
                                inc(r);
                                q[r].x:=x;
                                q[r].y:=y;
                                if (x=fn.x) and (y=fn.y) then exit(true);
                        end;
                end;

        end;
        exit(false);
end;

procedure process;
var     left,right,mid:longint;
begin
        res:=0;
        left:=1;right:=dis[st.x,st.y];
        while left<=right do
        begin
                mid:=(left+right) shr 1;
                if bfsFind(mid) then
                begin
                        res:=mid;
                        left:=mid+1;
                end
                else    right:=mid-1;
        end;
end;

begin
        input;
        bfsDis;
        process;
        write(res);
end.

Code mẫu của RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       511;

var
  f1,f2         :       text;
  m,n           :       longint;
  a             :       array[1..MAXN,1..MAXN] of char;
  d             :       array[1..MAXN,1..MAXN] of longint;
  qu,qv         :       array[1..MAXN*MAXN] of longint;
  visited       :       array[1..MAXN,1..MAXN] of boolean;
  first,last    :       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;

var
  su,sv,tu,tv:longint;

procedure init;
    var
      u,v,uu,vv,di,dj:longint;
    begin
      first:=1; last:=0;
      for u:=1 to m do
      for v:=1 to n do
        if a[u,v]='+' then
          begin
            inc(last);
            qu[last]:=u; qv[last]:=v;
            d[u,v]:=1;
          end
        else if a[u,v]='V' then
          begin
            su:=u;
            sv:=v;
          end
        else if a[u,v]='J' then
          begin
            tu:=u;
            tv:=v;
          end;

      while first<=last do
        begin
          u:=qu[first]; v:=qv[first]; inc(first);
          for di:=-1 to 1 do
          for dj:=-1 to 1 do
            if di*di+dj*dj=1 then
              begin
                uu:=u+di; vv:=v+dj;
                if (uu>0) and (uu<=m) and (vv>0) and (vv<=n) and (d[uu,vv]=0) then
                  begin
                    inc(last);
                    qu[last]:=uu; qv[last]:=vv;
                    d[uu,vv]:=d[u,v]+1;
                  end;
              end;
        end;
    end;

function check(val:longint):boolean;
    var
      u,v,uu,vv,di,dj:longint;
    begin
      if val>d[su,sv] then exit(false);
      first:=1; last:=1; qu[first]:=su; qv[first]:=sv;
      fillchar(visited,sizeof(visited),false); visited[su,sv]:=true;
      while first<=last do
        begin
          u:=qu[first]; v:=qv[first]; inc(first);
          for di:=-1 to 1 do
          for dj:=-1 to 1 do
            if (di*di+dj*dj=1) then
              begin
                uu:=u+di; vv:=v+dj;
                if (uu>0) and (uu<=m) and (vv>0) and (vv<=n) and (not visited[uu,vv])
                and (d[uu,vv]>=val) then
                  begin
                    if (uu=tu) and (vv=tv) then exit(true);
                    visited[uu,vv]:=true;
                    inc(last);
                    qu[last]:=uu; qv[last]:=vv;
                  end;
              end;
        end;
      exit(false);
    end;

procedure solve;
    var
      l,r,mid,res:longint;
    begin
      res:=0; l:=0; r:=MAXN*2;
      while l<=r do
        begin
          mid:=(l+r) shr 1;
          if check(mid) then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      if res>0 then dec(res);
      writeln(f2,res);
    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 505
#define maxe 100005

string s[505];
int d[505][505], rs, cs, rf, cf;
II que[505 * 505]; 
int n, m;
bool flag[505][505] = {0};

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

void bfs(){
    ms(d, -1);
    int size = 0;
    Rep(i, n) Rep(j, m){
        if(s[i][j] == '+'){
            d[i][j] = 0;
            que[size++] = mp(i, j);
        }
    }
    int r, c, rr, cc;
    Rep(i, size){
        r = que[i].fi, c = que[i].se;
        Rep(t, 4){
            rr = r + dr[t]; cc = c + dc[t];
            if(thoaman(rr, cc) && d[rr][cc] == -1){
                d[rr][cc] = d[r][c] + 1;
                que[size++] = mp(rr, cc);
            }
        }
    }
}

bool go(int x){
    //cout << x << endl;
    ms(flag, 0);
    flag[rs][cs] = 1;
    int size = 0;
    que[size++] = mp(rs, cs);
    int r, c, rr, cc;

    Rep(i, size){

        r = que[i].fi, c = que[i].se;
        //cout << r << " " << c << endl;
        Rep(t, 4){
            rr = r + dr[t]; cc = c + dc[t];
            if(thoaman(rr, cc) && d[rr][cc] >= x && !flag[rr][cc]){
                flag[rr][cc] = 1;
                que[size++] = mp(rr, cc);
            }
        }
    }
    return flag[rf][cf];
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    scanf("%d %d", &n, &m);
    Rep(i, n){
        cin >> s[i];
        Rep(j, m){
            if(s[i][j] == 'V') {rs = i; cs = j;}
            if(s[i][j] == 'J') {rf = i; cf = j;}
        }
    }
    bfs();
    int u = 0, v = min(d[rs][cs], d[rf][cf]) + 1, mid;
   // go(3);
    //printf("%b\n", go(3));
    while(u < v){
        mid = (u + v) >> 1;
        if(go(mid)) u = mid + 1;
        else v = mid;
    }
    cout << (--u) << endl;
}

Code mẫu của ll931110

program vukvn;
const
  input  = '';
  output = '';
  maxn = 500;
  maxv = 500 * 500;
  dx: array[1..4] of longint = (-1,0,1,0);
  dy: array[1..4] of longint = (0,1,0,-1);
var
  d: array[1..maxn,1..maxn] of longint;
  qx,qy: array[1..maxv] of longint;
  free: array[1..maxn,1..maxn] of boolean;
  sx,sy,fx,fy: longint;
  n,m,res: longint;

procedure init;
var
  f: text;
  i,j: longint;
  ch: char;
begin
  assign(f, input);
    reset(f);

  readln(f, m, n);
  for i := 1 to m do
    for j := 1 to n do d[i,j] := -1;

  for i := 1 to m do
    begin
      for j := 1 to n do
        begin
          read(f, ch);
          if ch = 'J' then
            begin sx := i;  sy := j; end
          else if ch = 'V' then
            begin fx := i;  fy := j; end
          else if ch = '+' then d[i,j] := 0;
        end;
      readln(f);
    end;

  close(f);
end;

function valid(kx,ky: longint): boolean;
begin
  valid := (1 <= kx) and (kx <= m) and (1 <= ky) and (ky <= n);
end;

procedure BFS;
var
  front,rear: longint;
  kx,ky,k: longint;
  i,j,u,v: longint;
begin
  front := 1;
  rear := 0;
  for i := 1 to m do
    for j := 1 to n do if d[i,j] = 0 then
      begin
        inc(rear);
        qx[rear] := i; qy[rear] := j;
      end;

  repeat
    u := qx[front];  v := qy[front];
    inc(front);

    for k := 1 to 4 do
      begin
        kx := u + dx[k];
        ky := v + dy[k];

        if valid(kx,ky) and (d[kx,ky] = -1) then
          begin
            inc(rear);
            qx[rear] := kx;  qy[rear] := ky;
            d[kx,ky] := d[u,v] + 1;
          end;
      end;
  until front > rear;
end;

function find(x: longint): boolean;
var
  u,v,kx,ky,k: longint;
  front,rear: longint;
begin
  if d[sx,sy] < x then exit(false);

  fillchar(free, sizeof(free), true);
  front := 1;  rear := 1;
  qx[1] := sx;  qy[1] := sy;
  free[sx,sy] := false;

  repeat
    u := qx[front];  v := qy[front];
    inc(front);

    for k := 1 to 4 do
      begin
        kx := u + dx[k];
        ky := v + dy[k];

        if valid(kx,ky) and free[kx,ky] and (d[kx,ky] >= x) then
          begin
            if (kx = fx) and(ky = fy) then exit(true);
            inc(rear);
            free[kx,ky] := false;
            qx[rear] := kx;  qy[rear] := ky;
          end;
      end;
  until front > rear;

  find := false;
end;

procedure solve;
var
  inf,sup,med: longint;
begin
  res := 0;
  inf := 0;
  sup := 2 * maxn;

  repeat
    med := (inf + sup) div 2;
    if find(med) then
      begin
        res := med;  inf := med + 1;
      end
    else sup := med - 1;
  until inf > sup;
end;

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

begin
  init;
  BFS;
  solve;
  printresult;
end.

Code mẫu của khuc_tuan

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

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair

typedef pair<int,int> PII;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int m, n;
char a[505][505];
int dist[505][505], vs[505][505];

int main() {
    scanf("%d%d", &m, &n);
    gets(a[0]);
    for(int i=0;i<m;++i) gets(a[i]);
    queue<PII> q;
    PII st, en;
    memset( dist, 0x1f, sizeof(dist));
    for(int i=0;i<m;++i) for(int j=0;j<n;++j) 
        if(a[i][j] == '+') {
            q.push(make_pair(i,j));
            dist[i][j] = 0;
        }
        else if(a[i][j] == 'V')
            st = make_pair(i,j);
        else if(a[i][j] == 'J')
            en = make_pair(i,j);
    while(!q.empty()) {
        int u = q.front().first;
        int v = q.front().second;
        q.pop();
        for(int h=0;h<4;++h) {
            int x = u + dx[h];
            int y = v + dy[h];
            if(0 <= x && x < m && 0 <= y && y < n && dist[x][y] > dist[u][v] + 1) {
                dist[x][y] = dist[u][v] + 1;
                q.push(make_pair(x,y));
            }
        }
    }
    int L = 0, R = 1010;
    while(L < R) {
        int M = (L+R) / 2 + 1;
        memset( vs, 0, sizeof(vs));
        while(!q.empty()) q.pop();
        if(dist[st.first][st.second] >= M) {
            vs[st.first][st.second] = true;
            q.push(st);
        }
        while(!q.empty()) {
            int u = q.front().first;
            int v = q.front().second;
            q.pop();
            for(int h=0;h<4;++h) {
                int x = u + dx[h];
                int y = v + dy[h];
                if(0 <= x && x < m && 0 <= y && y < n && !vs[x][y] && dist[x][y] >= M) {
                    vs[x][y] = true;
                    q.push(make_pair(x,y));
                }
            }
        }
        if(vs[en.first][en.second]) L = M;
        else R = M - 1;
    }
    cout << L << endl;
    return 0;
}