Editorial for VOI 06 Bài 2 - Quân tượng
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=205; dx:array[1..4] of longint=(-1,-1,1,1); dy:array[1..4] of longint=(-1,1,1,-1); var n,m,sx,sy,fx,fy:longint; a,d:array[1..maxn,1..maxn] of longint; q:array[0..1,0..maxn*maxn,0..1] of longint; num:array[0..1] of longint; procedure rf; var i,x,y:longint; begin assign(input,fi); reset(input); readln(n,m,sx,sy,fx,fy); fillchar(a,sizeof(a),0); fillchar(d,sizeof(d),0); for i:=1 to m do begin readln(x,y); a[x,y]:=1; end; close(input); end; function check(x,y:longint):boolean; begin check:=(x>0) and (y>0) and (x<=n) and (y<=n) and (a[x,y]=0); end; procedure pr; var i,j,cur,x,y,xt,yt:longint; kt:boolean; begin if (sx+sy+fx+fy) mod 2 = 1 then exit; d[sx,sy]:=1; i:=1; num[1]:=1; cur:=1; q[cur,1,0]:=sx; q[cur,1,1]:=sy; repeat num[1-cur]:=0; if num[cur]=0 then break; for i:=1 to num[cur] do begin x:=q[cur,i,0]; y:=q[cur,i,1]; for j:=1 to 4 do begin xt:=x; yt:=y; repeat kt:=true; xt:=xt+dx[j]; yt:=yt+dy[j]; if check(xt,yt) then begin if d[xt,yt]=0 then begin inc(num[1-cur]); q[1-cur,num[1-cur],0]:=xt; q[1-cur,num[1-cur],1]:=yt; d[xt,yt]:=d[x,y]+1; end; end else kt:=false; until not kt; end; end; cur:=1-cur; until d[fx,fy]>0; end; procedure wf; begin assign(output,fo); rewrite(output); if d[fx,fy]=0 then write(-1) else write(d[fx,fy]-1); close(output); end; begin rf; pr; wf; 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; #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(); it != _e; ++it) #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 205 bool check[N][N], cant[N][N]; int p, q, s, t, n, m; //(p,q): diem dau, (s,t): diem cuoi queue<ii> qu; void process(int i, int j) { if(check[i][j]==0) { check[i][j] = 1; qu.push(ii(i,j)); } } void printQueue(queue<ii> qu) { for(;!qu.empty(); printf( "(%d;%d) ", qu.front().fi, qu.front().se ), qu.pop() ); putchar(10); } int main() { //freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); scanf( "%d%d%d%d%d%d", &n, &m, &p, &q, &s, &t ); rep(i, m) { int u, v; scanf( "%d%d", &u, &v ); cant[u][v] = 1; } qu.push(ii(p, q)); check[p][q] = 1; for( int step = 0; !qu.empty(); ++step ) { //printQueue(qu); rep(k, qu.size()) { int u = qu.front().fi, v = qu.front().se; qu.pop(); if( u == s && v == t ) { printf( "%d\n", step ); return 0; } for(int i=u-1, j=v-1; cant[i][j]==0&&i>0&&j>0; --i,--j) process(i,j); for(int i=u+1, j=v+1; cant[i][j]==0&&i<=n&&j<=n; ++i,++j) process(i,j); for(int i=u+1, j=v-1; cant[i][j]==0&&i<=n&&j>0; ++i,--j) process(i,j); for(int i=u-1, j=v+1; cant[i][j]==0&&i>0&&j<=n; --i,++j) process(i,j); } } printf( "-1\n" ); return 0; }
Code mẫu của ladpro98
program qbbishop; uses math; type e=record x,y:longint; end; const d:array[1..4,1..2] of longint = ((1,1),(-1,1),(1,-1),(-1,-1)); maxn=444; oo=123456789; fi=''; var a:array[1..maxn,1..maxn] of longint; check:array[1..maxn,1..maxn] of boolean; n,m,p,q,s,t:longint; qu:array[1..maxn*maxn] of e; procedure input; var inp:text; i,x,y:longint; begin assign(inp,fi); reset(inp); readln(inp,n,m,q,p,t,s); for i:=1 to m do begin readln(inp,x,y); check[y,x]:=true; end; close(inp); end; function outBound(i,j:longint):boolean; begin if (1<=i) and (i<=n) and (1<=j) and (j<=n) then exit(false); exit(true); end; procedure bfs; var i,j,t,l,r,x,y:longint; st:e; begin for i:=1 to n do for j:=1 to n do a[i,j]:=oo; l:=1;r:=1; qu[1].x:=p; qu[1].y:=q; a[p,q]:=0; while l<=r do begin st:=qu[l]; inc(l); for t:=1 to 4 do begin x:=0; y:=0; while true do begin inc(x); inc(y); i:=st.x+x*d[t][1]; j:=st.y+y*d[t][2]; if (outBound(i,j)) or (check[i,j]) then break; if a[i,j]=oo then begin a[i,j]:=a[st.x,st.y]+1; inc(r); qu[r].x:=i; qu[r].y:=j; end; end; end; end; end; begin input; bfs; if a[s,t] = oo then write(-1) else write(a[s,t]); end.
Code mẫu của RR
{$R+,Q+} const FINP=''; FOUT=''; MAXN=201; di:array[1..4] of longint=(-1,-1,1,1); dj:array[1..4] of longint=(-1,1,-1,1); var top1,top2,m,n,p,q,s,t:longint; a,xet,d:array[1..MAXN,1..MAXN] of longint; su1,sv1,su2,sv2:array[1..MAXN*MAXN] of longint; procedure inp; var f:text; i,u,v:longint; begin assign(f,FINP); reset(f); read(f,n,m,p,q,s,t); for i:=1 to m do begin read(f,u,v); a[u,v]:=1; end; close(f); if (p+q) mod 2<>(s+t) mod 2 then begin writeln(-1); halt; end; if (p=s) and (q=t) then begin writeln(-1); halt; end; end; procedure ans; var f:text; begin assign(f,FOUT); rewrite(f); if d[s,t]=0 then writeln(f,-1) else writeln(f,d[s,t]); close(f); end; procedure solve; var u,v,h,i,uu,vv:longint; begin top1:=1; su1[1]:=p; sv1[1]:=q; d[p,q]:=0; xet[p,q]:=1; while top1>0 do begin top2:=0; for i:=1 to top1 do begin u:=su1[i]; v:=sv1[i]; for h:=1 to 4 do begin uu:=u; vv:=v; while true do begin uu:=uu+di[h]; vv:=vv+dj[h]; if (uu=0) or (vv=0) or (uu=n+1) or (vv=n+1) then break; if (a[uu,vv]=1) then break; if (xet[uu,vv]=1) then continue; xet[uu,vv]:=1; d[uu,vv]:=d[u,v]+1; if xet[s,t]=1 then exit; inc(top2); su2[top2]:=uu; sv2[top2]:=vv; end; end; end; top1:=top2; su1:=su2; sv1:=sv2; end; end; begin inp; solve; ans; end.
Code mẫu của ll931110
Program QBBISHOP; Type rec = record x,y: longint; End; Var a: array[0..201,0..201] of boolean; d: array[1..200,1..200] of longint; dx,dy: array[1..4] of longint; queue: array[1..40000] of rec; n,m,p,q,s,t: longint; Procedure init; Var i,u,v: longint; Begin Fillchar(a, sizeof(a), true); Readln(n, m, p, q, s, t); For i:= 0 to n + 1 do Begin a[i,0]:= false; a[0,i]:= false; a[i,n + 1]:= false; a[n + 1,i]:= false; End; For i:= 1 to m do Begin Readln(u, v); a[u,v]:= false; End; End; Procedure enter; Begin dx[1]:= -1; dx[2]:= 1; dx[3]:= 1; dx[4]:= -1; dy[1]:= 1; dy[2]:= 1; dy[3]:= -1; dy[4]:= -1; End; Procedure BFS; Var front,rear: longint; k,u,v,i,j: longint; Begin front:= 1; rear:= 1; d[p,q]:= 0; queue[1].x:= p; queue[1].y:= q; Repeat u:= queue[front].x; v:= queue[front].y; inc(front); For k:= 1 to 4 do Begin i:= u; j:= v; While a[i,j] do Begin i:= i + dx[k]; j:= j + dy[k]; If a[i,j] and (d[i,j] = 0) and ((i <> p) or (j <> q)) then Begin inc(rear); queue[rear].x:= i; queue[rear].y:= j; d[i,j]:= d[u,v] + 1; If (i = s) and (j = t) then exit; End; End; End; Until front > rear; End; Procedure solve; Begin If odd(p + q - s - t) then Begin Writeln(-1); Exit; End; BFS; If d[s,t] = 0 then writeln(-1) else writeln(d[s,t]); End; Begin init; enter; solve; End.
Code mẫu của skyvn97
#include<stdio.h> #include<queue> #define x first #define y second #define MAX 222 using namespace std; typedef pair<int,int> ii; int c[MAX][MAX]; int l[MAX][MAX]; int m,n; ii f,s; int dx[]={-1,-1,1,1}; int dy[]={-1,1,-1,1}; void init(void) { int i,j,x,y; scanf("%d",&n); scanf("%d",&m); scanf("%d",&x); scanf("%d",&y); s=ii(x,y); scanf("%d",&x); scanf("%d",&y); f=ii(x,y); for (i=1;i<=n;i=i+1) for (j=1;j<=n;j=j+1) { c[i][j]=0; l[i][j]=0; } for (i=1;i<=m;i=i+1) { scanf("%d",&x); scanf("%d",&y); c[x][y]=3; } for (i=0;i<=n+1;i=i+1) { c[i][0]=2; c[0][i]=2; c[n+1][i]=2; c[i][n+1]=2; } } void BFS(void) { queue<ii> q; ii p; int i,j; q.push(s); c[s.x][s.y]=1; while (!q.empty()) { p=q.front(); q.pop(); if (p==f) { printf("%d",l[f.x][f.y]); return; } for (i=0;i<4;i=i+1) for (j=1;j<=n;j=j+1) { if (c[p.x+j*dx[i]][p.y+j*dy[i]]>1) break; if (c[p.x+j*dx[i]][p.y+j*dy[i]]==0) { l[p.x+j*dx[i]][p.y+j*dy[i]]=l[p.x][p.y]+1; c[p.x+j*dx[i]][p.y+j*dy[i]]=1; q.push(ii(p.x+j*dx[i],p.y+j*dy[i])); } } } printf("-1"); } int main(void) { init(); BFS(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <queue> using namespace std; typedef pair<int,int> PII; int n, m; PII st, en; bool a[222][222]; int f[222][222]; int main() { scanf("%d%d%d%d%d%d", &n, &m, &st.first, &st.second, &en.first, &en.second); for(int i=0;i<m;++i) { int x, y; scanf("%d%d", &x, &y); a[x][y] = true; } memset( f, 0x3f, sizeof(f)); f[st.first][st.second] = 0; queue<PII> q; q.push(st); while(!q.empty()) { PII u = q.front(); int tmp = f[u.first][u.second]; q.pop(); for(int dx=-1;dx<=1;dx+=2) for(int dy=-1;dy<=1;dy+=2) { PII v = u; while(true) { v.first += dx; v.second += dy; if(v.first<1 || v.first>n || v.second<1 || v.second>n) break; if(a[v.first][v.second]) break; if(f[v.first][v.second]>tmp+1) { f[v.first][v.second] = tmp + 1; q.push(v); } } } } int tmp = f[en.first][en.second]; if(tmp>1000000) cout << -1 << endl; else cout << tmp << endl; //system("pause"); return 0; }
Comments