Editorial for ICEFROG

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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
num:=0;
for i:=1 to m do
begin
for j:=1 to n do
begin
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;
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);
for i:=1 to n do
for j:=1 to m do
avail[i,j]:=true;
for i:=1 to n do
begin
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
for i:=1 to m do
begin
for j:=1 to n do
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);

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
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;
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;
}