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