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.

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);
fillchar(a,sizeof(a),0);
fillchar(d,sizeof(d),0);
for i:=1 to m do
begin
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;
}

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);
for i:=1 to m do
begin
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);
for i:=1 to m do
begin
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
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;
}