Nguồn đề bài: http://vn.spoj.com/problems/QBBISHOP/
1. Đề bài QBBISHOP spoj
Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.
Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,…, m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân
Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.
Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.
Input
Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t.
Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.
Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Output
Gồm 1 dòng duy nhất là số nước đi tìm được
Example
Input:
8 3 7 2 1 4
5 4
3 4
4 7
Output:
3
2. Thuật toán QBBISHOP spoj
Xem mỗi ô (i, j) như là 1 đỉnh của đồ thị. 2 đỉnh (x1, y1) và (x2, y2) có cạnh nối nếu (x1 – y1 = x2 – y2) hoặc (x1 + y1 = x2 + y2), tức là cùng nằm trên 1 trong 2 đường chéo. Sau đó BFS như thường.
3. code tham khảo QBBISHOP spoj
[sociallocker]
const fi='';
nmax=205;
cld:array[1..4] of shortint=(1,1,-1,-1);
clc:array[1..4] of shortint=(1,-1,1,-1);
type
data=longint;
dulieu=record
u,v:data;
end;
var
f:text;
A:array[0..nmax+1,0..nmax+1] of byte;
m,n,s,t,q,p:data;
C:array[0..nmax+1,0..nmax+1] of data;
H:array[0..nmax*nmax] of dulieu;
dau,cuoi:data;
procedure docfile;
var i,j,u,v:data;
begin
assign(f,fi); reset(f);
readln(f,n,m,p,q,s,t);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=0;
for i:=0 to n +1 do
begin
A[0,i]:=3;
A[n+1,i]:=3;
A[i,0]:=3;
a[i,n+1]:=3;
end;
for i:=1 to m do
begin
readln(f,u,v);
a[u,v]:=2;
end;
close(f);
end;
procedure themvao(x,y:data);
begin
inc(cuoi);
H[cuoi].u:=x;
H[cuoi].v:=y;
end;
procedure layra(var x,y:data);
begin
x:=H[dau].u;
y:=H[dau].v;
inc(dau);
end;
procedure go(x,y,k:data);
var u,v:data;
begin
u:=x;
v:=y;
while a[u,v]<>3 do
begin
if (A[u,v]=0) then
begin
c[u,v]:=c[x,y]+1;
themvao(u,v);
a[u,v]:=1;
end;
if a[u,v]=2 then
exit;
if (u=s) and (v=t) then
begin
writeln(c[s,t]);
readln;
halt;
end;
u:=u+cld[k];
v:=v+clc[k];
end;
end;
procedure bfs;
var i,j,x,y:data;
begin
dau:=1;
cuoi:=0;
themvao(p,q);
a[p,q]:=1;
for i:=1 to n do
for j:=1 to n do
C[i,j]:=0;
while not (dau>cuoi) do
begin
layra(x,y);
for i:=1 to 4 do
go(x,y,i);
end;
if c[s,t]=0 then
writeln('-1');
end;
begin
docfile;
bfs;
end.
[/sociallocker]
