QBBISHOP – spoj

Đề bài: [xem đề bài]

Thuật toán:

• BFS từ ô (s.x,s.y)
• Mỗi lần BFS lấy ra ô (u,v) đi theo 4 đường chéo có dạng (u-x,v-x) , (u-x,v+x) , (u+x,v-x) , (u+x,v+x).
• Đừng quên là không thể đi đến ô đang có cờ.

Code: [xem code]

const   fi='';
        fo='';
        maxn=200;
        dx:array[1..4] of integer =(1,-1,1,-1);
        dy:array[1..4] of integer =(1,1,-1,-1);
type    point=record
                x,y:integer;
                end;
var     free:array[0..maxn+1,0..maxn+1] of boolean;
        bac:array[0..maxn+1,0..maxn+1] of integer;
        q:array[1..maxn*maxn] of point;
        n,m,i,j:integer;
        s,f:point;
        dau,cuoi,res:longint;
procedure nhap;
var     x,y:integer;
begin
    assign(input,fi);reset(input);
    readln(n,m,s.x,s.y,f.x,f.y);
    fillchar(free,sizeof(free),false);
    for i:=1 to n do
        for j:=1 to n do free[i,j]:=true;
    for i:=1 to m do
        begin
            readln(x,y);
            free[x,y]:=false;
        end;
end;
procedure init;
begin

end;
procedure push(x,y:integer);
begin
    inc(cuoi);
    q[cuoi].x:=x;
    q[cuoi].y:=y;
end;
procedure bfs;
var     u,v:point;
begin
    dau:=1;cuoi:=1;
    q[1].x:=s.x;q[1].y:=s.y;
    while dau<=cuoi do
        begin
            u:=q[dau]; inc(dau);
            for i:=1 to 4 do
                for j:=1 to n do
                        begin
                            v.x:=dx[i]*j+u.x;
                            v.y:=dy[i]*j+u.y;
                            if (v.x=f.x) and (v.y=f.y) then
                                begin
                                        res:=bac[u.x,u.y]+1;
                                        exit;
                                end;
                            if (v.x>=1) and (v.y>=1) and (v.x<=n) and (v.y<=n) and (free[v.x,v.y])  then
                                begin
                                   bac[v.x,v.y]:=bac[u.x,u.y] +1;
                                   free[v.x,v.y]:=false;
                                   push(v.x,v.y);
                                end else break;
                        end;
        end;
    res:=-1;exit;
end;
procedure xuly;
begin
    if (s.x+s.y) mod 2<>(f.x+f.y) mod 2 then begin res:=-1; exit; end;
    bfs;

end;
procedure inkq;
begin
    assign(output,fo);rewrite(Output);

    writeln(res);

    close(output);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.