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);
     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

Please read the guidelines before commenting.


There are no comments at the moment.