Editorial for Hồ Thiên Nga
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.
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 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; }
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> #include <queue> using namespace std; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; int m, n, inf; char a[1505][1505]; short f[1500][1500]; bool inq[1500][1500], g[1500][1500]; int qx1[1500*1500], qy1[1500*1500], qx2[1500*1500], qy2[1500*1500]; int L, R; int *qx, *qy; int sx, sy, ex, ey; int main() { scanf("%d%d", &m, &n); gets(a[0]); for(int i=0;i<m;++i) gets(a[i]); sx = -1; memset( f, 0x1f, sizeof(f)); inf = f[0][0]; R = -1; qx = qx1; qy = qy1; for(int i=0;i<m;++i) for(int j=0;j<n;++j) { if(a[i][j]!='X') { qx[++R] = i; qy[R] = j; f[i][j] = 0; } if(a[i][j]=='L') { if(sx==-1) sx = i, sy = j; else ex = i, ey = j; } } while(L<=R) { int ux = qx[L]; int uy = qy[L++]; for(int h=0;h<4;++h) { int x = ux + dx[h]; int y = uy + dy[h]; if(x<0 || x>=m || y<0 || y>=n) continue; if(f[x][y]==inf) { f[x][y] = f[ux][uy] + 1; qx[++R] = x; qy[R] = y; } } } L = 0; R = 0; qx[0] = sx; qy[0] = sy; g[sx][sy] = true; int * tqx = qx2; int * tqy = qy2; int res; for(res=0;;++res) { int l2 = 0, r2 = -1; while(L <= R) { int ux = qx[L]; int uy = qy[L++]; for(int h=0;h<4;++h) { int x = ux + dx[h]; int y = uy + dy[h]; if(x<0 || x>=m || y<0 || y>=n) continue; if(f[x][y]<=res) { if(!g[x][y]) { g[x][y] = true; qx[++R] = x; qy[R] = y; } } else { if(!inq[x][y]) { inq[x][y] = true; tqx[++r2] = x; tqy[r2] = y; } } } } swap(qx,tqx); swap(qy,tqy); L = l2; R = r2; if(g[ex][ey]) break; } printf("%d\n", res); //system("pause"); return 0; }
Comments