Hướng dẫn giải của VOI 06 Bài 2 - Quân tượng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận