Editorial for Cijevi


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 maxn=25;
      dx:array[1..4] of shortint=(-1,0,1,0);
      dy:array[1..4] of shortint=(0,1,0,-1);
var m,n,rex,rey,x,y,x1,y1,pre,pre1:byte;
    rec:char;
    s:array[0..1,0..1] of byte;
    a:array[1..maxn,1..maxn,1..maxn,1..maxn] of byte;
    b:array[1..maxn,1..maxn] of char;
    d:array[1..maxn,1..maxn] of byte;
function max(a,b:byte):byte;
begin
     if a>b then max:=a else max:=b;
end;
procedure rf;
var i,j:byte; c:char;
begin
     fillchar(a,sizeof(a),0);
     readln(m,n);
     for i:=1 to m do
     begin
          for j:=1 to n do
          begin
               read(c);
               b[i,j]:=c;
               if c='M' then
               begin
                    s[0,0]:=i; s[0,1]:=j;
               end;
               if c='Z' then
               begin
                    s[1,0]:=i; s[1,1]:=j;
               end;
               if (c='|') or (c='+') or (c='1') or (c='4') then
               begin
                    a[i,j,i+1,j]:=1;
                    a[i+1,j,i,j]:=1;
               end;
               if (c='|') or (c='+') or (c='2') or (c='3') then
               begin
                    a[i,j,i-1,j]:=1;
                    a[i-1,j,i,j]:=1;
               end;
               if (c='-') or (c='+') or (c='1') or (c='2') then
               begin
                    a[i,j,i,j+1]:=1;
                    a[i,j+1,i,j]:=1;
               end;
               if (c='-') or (c='+') or (c='3') or (c='4') then
               begin
                    a[i,j,i,j-1]:=1;
                    a[i,j-1,i,j]:=1;
               end;
          end;
          readln;
     end;
     fillchar(d,sizeof(d),0);
end;

function check(p,q:byte):boolean;
begin
     check:=(p>0) and (q>0) and (p<=m) and (q<=n);
end;

procedure go(k:byte);
var j,xt,yt:byte; kt:boolean;
begin
     x:=s[k,0]; y:=s[k,1];
     d[x,y]:=1;
     for j:=1 to 4 do
     begin
          xt:=x+dx[j]; yt:=y+dy[j];
          if check(xt,yt) and (a[x,y,xt,yt]=1) then
          begin
               a[x,y,xt,yt]:=0;
               a[xt,yt,x,y]:=0;
               x:=xt; y:=yt;
               d[x,y]:=1;
               pre:=j;
               break;
          end;
     end;
     while true do
     begin
          if b[x,y]='+' then
          begin
               xt:=x+dx[pre]; yt:=y+dy[pre];
               if (a[x,y,xt,yt]=1) and (b[xt,yt]<>'.') then
               begin
                    a[x,y,xt,yt]:=0;
                    a[xt,yt,x,y]:=0;
                    x:=xt; y:=yt;
                    d[x,y]:=1;
               end
               else break;
          end
          else
          begin
               kt:=false;
               for j:=1 to 4 do
               begin
                    xt:=x+dx[j]; yt:=y+dy[j];
                    if check(xt,yt) and (a[x,y,xt,yt]=1) and (b[xt,yt]<>'.') then
                    begin
                         a[x,y,xt,yt]:=0;
                         a[xt,yt,x,y]:=0;
                         x:=xt; y:=yt;
                         pre:=j;
                         d[x,y]:=1;
                         kt:=true;
                         break;
                    end;
               end;
               if not kt then break;
          end;
     end;
     if b[x,y]='1' then
     begin
          if pre=4 then pre:=3 else pre:=2;
     end;
     if b[x,y]='2' then
     begin
          if pre=3 then pre:=2 else pre:=1;
     end;
     if b[x,y]='3' then
     begin
          if pre=2 then pre:=1 else pre:=4;
     end;
     if b[x,y]='4' then
     begin
          if pre=1 then pre:=4 else pre:=3;
     end;
end;

procedure pr;
var i,j:byte; kt:boolean;
begin
     go(0);
     x1:=x; y1:=y; pre1:=pre;
     go(1);
     kt:=false;
     for i:=1 to m do
         for j:=1 to n do
             if (d[i,j]=0) and (b[i,j]<>'.') then kt:=true;
     if x=x1 then
     begin
          rex:=x;
          rey:=(y+y1) div 2;
          rec:='-';
     end;
     if y=y1 then
     begin
          rex:=(x+x1) div 2;
          rey:=y;
          rec:='|';
     end;
     if x1+y1=x+y then
     begin
          if (pre=3) or (pre1=3) then
          begin
               rex:=max(x,x1);
               rey:=max(y,y1);
               rec:='3';
          end
          else
          begin
               rex:=x+x1-max(x,x1);
               rey:=y+y1-max(y,y1);
               rec:='1';
          end;
     end;
     if x1+y=x+y1 then
     begin
          if (pre=3) or (pre1=3) then
          begin
               rex:=max(x,x1);
               rey:=y+y1-max(y,y1);
               rec:='2';
          end
          else
          begin
               rex:=x+x1-max(x,x1);
               rey:=max(y,y1);
               rec:='4';
          end;
     end;
     if kt then rec:='+';
end;

procedure wf;
begin
     write(rex,' ',rey,' ',rec);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của RR

{$R+,Q+}
{$mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=30;
var
  f1,f2:text;
  lu,lv,m,n,startu,startv,targetu,targetv:longint;
  lc:char;
  ok,ok2:boolean;
  a:array[1..MAXN,1..MAXN] of char;
  xet:array[-1..MAXN,-1..MAXN] of longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1);
  close(f2);
end;
procedure inp;
var
  i,j:longint;
begin
  readln(f1,m,n);
  for i:=1 to m do
    begin
      for j:=1 to n do
        begin
          read(f1,a[i,j]);
          if a[i,j]='M' then
            begin startu:=i; startv:=j; end;
          if a[i,j]='Z' then
            begin targetu:=i; targetv:=j; end;
        end;
      readln(f1);
    end;
end;
procedure ans;
begin
  writeln(f2,lu,' ',lv,' ',lc);
end;
function check(u,v,h:longint):boolean; inline;
begin
  if (u<=0) or (v<=0) or (u>m) or (v>n) then exit(false);
  if a[u,v]='Z' then exit(true);
  if a[u,v]='M' then exit(true);
  case h of
    1: if a[u,v] in ['2','3','|','+'] then exit(true) else exit(false);
    2: if a[u,v] in ['1','2','-','+'] then exit(true) else exit(false);
    3: if a[u,v] in ['1','4','|','+'] then exit(true) else exit(false);
    4: if a[u,v] in ['3','4','-','+'] then exit(true) else exit(false);
  end;
end;
procedure visit(u,v:longint);
begin
  if (u<=0) or (v<=0) or (u>m) or (v>n) then exit;
  if xet[u,v]=1 then exit; xet[u,v]:=1;
  case a[u,v] of
    'M': begin
           if (u>1) and (a[u-1,v]<>'.') then visit(u-1,v);
           if (u<m) and (a[u+1,v]<>'.') then visit(u+1,v);
           if (v>1) and (a[u,v-1]<>'.') then visit(u,v-1);
           if (v<n) and (a[u,v+1]<>'.') then visit(u,v+1);
         end;
    '|': begin
           if ok2 then ok2:=check(u-1,v,3);
           if ok2 then ok2:=check(u+1,v,1);
           if (xet[u-1,v]=0) then visit(u-1,v);
           if (xet[u+1,v]=0) then visit(u+1,v);
         end;
    '-': begin
           if ok2 then ok2:=check(u,v-1,2);
           if ok2 then ok2:=check(u,v+1,4);
           if (xet[u,v-1]=0) then visit(u,v-1);
           if (xet[u,v+1]=0) then visit(u,v+1);
         end;
    '+': begin
           if ok2 then ok2:=check(u-1,v,3);
           if ok2 then ok2:=check(u+1,v,1);
           if ok2 then ok2:=check(u,v-1,2);
           if ok2 then ok2:=check(u,v+1,4);
           if (xet[u-1,v]=0) then visit(u-1,v);
           if (xet[u+1,v]=0) then visit(u+1,v);
           if (xet[u,v-1]=0) then visit(u,v-1);
           if (xet[u,v+1]=0) then visit(u,v+1);
         end;
    '1': begin
           if ok2 then ok2:=check(u,v+1,4);
           if ok2 then ok2:=check(u+1,v,1);
           if (xet[u,v+1]=0) then visit(u,v+1);
           if (xet[u+1,v]=0) then visit(u+1,v);
         end;
    '2': begin
           if ok2 then ok2:=check(u-1,v,3);
           if ok2 then ok2:=check(u,v+1,4);
           if (xet[u-1,v]=0) then visit(u-1,v);
           if (xet[u,v+1]=0) then visit(u,v+1);
         end;
    '3': begin
           if ok2 then ok2:=check(u-1,v,3);
           if ok2 then ok2:=check(u,v-1,2);
           if (xet[u-1,v]=0) then visit(u-1,v);
           if (xet[u,v-1]=0) then visit(u,v-1);
         end;
    '4': begin
           if ok2 then ok2:=check(u,v-1,2);
           if ok2 then ok2:=check(u+1,v,1);
           if (xet[u,v-1]=0) then visit(u,v-1);
           if (xet[u+1,v]=0) then visit(u+1,v);
         end;
    '.': begin
           lu:=u;
           lv:=v;
         end;
    'Z': ok:=true;
  end;
end;
procedure solve;
var
  tu,tv:longint;
begin
  visit(startu,startv);
  tu:=lu; tv:=lv;
  //Xet +
  ok:=false; ok2:=true; fillchar(xet,sizeof(xet),0);
  lu:=0; a[tu,tv]:='+';
  visit(startu,startv);
  if (lu=0) and ok and ok2 then
    begin lu:=tu; lv:=tv; lc:='+'; exit; end;
  //Xet |
  ok:=false; ok2:=true;
  fillchar(xet,sizeof(xet),0);
  lu:=0; a[tu,tv]:='|';
  visit(startu,startv);
  if (lu=0) and ok and ok2 then
    begin lu:=tu; lv:=tv; lc:='|'; exit; end;
  //Xet -
  ok:=false; ok2:=true;
  fillchar(xet,sizeof(xet),0);
  lu:=0; a[tu,tv]:='-';
  visit(startu,startv);
  if (lu=0) and ok and ok2 then
    begin lu:=tu; lv:=tv; lc:='-'; exit; end;
  //Xet 1
  ok:=false; ok2:=true;
  fillchar(xet,sizeof(xet),0);
  lu:=0; a[tu,tv]:='1';
  visit(startu,startv);
  if (lu=0) and ok and ok2 then
    begin lu:=tu; lv:=tv; lc:='1'; exit; end;
  //Xet 2
  ok:=false; ok2:=true;
  fillchar(xet,sizeof(xet),0);
  lu:=0; a[tu,tv]:='2';
  visit(startu,startv);
  if (lu=0) and ok and ok2 then
    begin lu:=tu; lv:=tv; lc:='2'; exit; end;
  //Xet 3
  ok:=false; ok2:=true;
  fillchar(xet,sizeof(xet),0);
  lu:=0; a[tu,tv]:='3';
  visit(startu,startv);
  if (lu=0) and ok and ok2 then
    begin lu:=tu; lv:=tv; lc:='3'; exit; end;
  //Xet 4
  ok:=false; ok2:=true;
  fillchar(xet,sizeof(xet),0);
  lu:=0; a[tu,tv]:='4';
  visit(startu,startv);
  if (lu=0) and ok and ok2 then
    begin lu:=tu; lv:=tv; lc:='4'; exit; end;
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
#include <cstring>
//#include <conio.h>


char a[30][30];
int n,m;

bool trai(int r,int c){ return ((c>=0) && (a[r][c-1]=='+' || a[r][c-1]=='-' || a[r][c-1]=='1' || a[r][c-1]=='2')); }
bool phai(int r,int c){ return ((c<m)&& (a[r][c+1]=='+' || a[r][c+1]=='-' || a[r][c+1]=='3' || a[r][c+1]=='4')); }
bool tren(int r,int c){ return ((r>=0) && (a[r-1][c]=='+' || a[r-1][c]=='|' || a[r-1][c]=='1' || a[r-1][c]=='4')); }
bool duoi(int r,int c){ return ((r<n) && (a[r+1][c]=='+' || a[r+1][c]=='|' || a[r+1][c]=='2' || a[r+1][c]=='3')); }

int main()
{
 //   freopen("CIJEVI.in","r",stdin);
    scanf("%d %d",&n,&m);
    for(int i = 0;i<n;i++)
        scanf("%s",a[i]);
    for(int i = 0;i<n;i++)
        for(int j = 0;j<m;j++)
        {
                if(a[i][j] == '.')
                {
                if(trai(i,j)&&phai(i,j)&&tren(i,j)&&duoi(i,j)) {printf("%d %d +",i+1,j+1); return 0;}
                if(trai(i,j)&&phai(i,j)) {printf("%d %d -",i+1,j+1); return 0;}
                if(tren(i,j)&&duoi(i,j)) {printf("%d %d |",i+1,j+1); return 0;}
                if(trai(i,j)&&duoi(i,j)) {printf("%d %d 4",i+1,j+1); return 0;}
                if(trai(i,j)&&tren(i,j)) {printf("%d %d 3",i+1,j+1); return 0;}
                if(phai(i,j)&&duoi(i,j)) {printf("%d %d 1",i+1,j+1); return 0;}
                if(phai(i,j)&&tren(i,j)) {printf("%d %d 2",i+1,j+1); return 0;}
                }
        }
   // getch();
}

Code mẫu của ll931110

Program CIJEVI;
Const
  input  = '';
  output = '';
  maxn = 25;
  d: array[1..6,1..2,1..2] of integer = (((1,2),(4,3)),((3,2),(4,1)),((2,1),(3,4)),((2,3),(1,4)),((2,2),(4,4)),((1,1),(3,3)));
  h: array[1..4,1..3] of integer = ((1,4,6),(3,4,5),(2,3,6),(1,2,5));
  dx: array[1..4] of integer = (-1,0,1,0);
  dy: array[1..4] of integer = (0,1,0,-1);
Var
  a: array[0..maxn + 1,0..maxn + 1] of char;
  t: array[1..7] of char;
  r,c,cx,cy: integer;
  sx,sy,fx,fy: integer;
  brnum,count: integer;
  check: boolean;

Procedure init;
Var
  f: text;
  i,j: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, r, c);
  For i:= 0 to r + 1 do
    For j:= 0 to c + 1 do a[i,j]:= '.';

  For i:= 1 to r do
    Begin
      For j:= 1 to c do
        Begin
          read(f, a[i,j]);
          If a[i,j] <> '.' then inc(brnum);
        End;
      Readln(f);
    End;

  t[1]:= '1';
  t[2]:= '2';
  t[3]:= '3';
  t[4]:= '4';
  t[5]:= '-';
  t[6]:= chr(124);
  t[7]:= '+';
End;

Procedure brway(var k: integer);
Var
  i,u: integer;
Begin
  u:= 0;
  For i:= 1 to 3 do
    if a[cx,cy] = t[h[k,i]] then
      Begin
        u:= h[k,i];
        break;
      End;

  If u = 0 then
    If a[cx,cy] <> '+' then
      Begin
        check:= false;
        exit;
      End
    else
      Begin
        cx:= cx + dx[k];
        cy:= cy + dy[k];
        exit;
      End;

  For i:= 1 to 2 do
    if k = d[u,i,1] then
      Begin
        k:= d[u,i,2];
        cx:= cx + dx[k];
        cy:= cy + dy[k];
        break;
      End;
End;

Function tk: boolean;
Begin
  tk:= ((cx = fx) and (cy = fy)) or not check;
End;

Function getbr(k: integer): integer;
Var
  i,u: integer;
  tx,ty,tmp,tmpcount: integer;
Begin
  tx:= cx;
  ty:= cy;

  For i:= 1 to 3 do
    Begin
      cx:= tx;
      cy:= ty;

      check:= true;
      u:= h[k,i];
      a[cx,cy]:= t[u];

      tmp:= k;
      tmpcount:= count;

      Repeat
        brway(tmp);
        If not tk then dec(tmpcount);
      Until ((cx = fx) and (cy = fy)) or not check;

      If (cx = fx) and (cy = fy) and (tmpcount < 2) then exit(u) else a[tx,ty]:= '.';
    End;

  getbr:= 7;
End;

Procedure solve;
Var
  f: text;
  k,i,j: integer;
Begin
  For i:= 1 to r do
    For j:= 1 to c do
      If a[i,j] = 'M' then
        Begin
          sx:= i;
          sy:= j;
        End
      else if a[i,j] = 'Z' then
        Begin
          fx:= i;
          fy:= j;
        End;

  For i:= 1 to 4 do
    Begin
      cx:= sx + dx[i];
      cy:= sy + dy[i];
      If (a[cx,cy] <> '.') and (a[cx,cy] <> 'Z') then
        Begin
          k:= i;
          break;
        End;
    End;

  count:= brnum - 2;
  Repeat
    brway(k);
    If a[cx,cy] <> '.' then dec(count);
  Until a[cx,cy] = '.';

  Assign(f, output);
    Rewrite(f);
    Write(f, cx, ' ', cy, ' ', t[getbr(k)]);
  Close(f);
End;

Begin
  init;
  solve;
End.

Code mẫu của khuc_tuan

//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
 {$mode delphi}

const
    dx : array[0..3] of integer = (-1,0,1,0);
    dy : array[0..3] of integer = (0,1,0,-1);

var
    z, x, y, h, i, j, m, n : integer;
    a : array[1..100,0..100] of char;
    mark : array[1..100,1..100] of integer;
    data : array[Char] of integer;
    ok : boolean;
    s : array[0..7] of char = '|-+1234'#0;

function inside(x,y : integer) : boolean;
begin
    inside := (x>=1) and (x<=m) and (y>=1) and (y<=n);
end;

procedure go(x,y,h : integer);
var
    nh, t, s : integer;
begin
    if a[x,y]='.' then
    begin
        mark[x,y] := mark[x,y] or (1 shl ((h+2) mod 4));
        exit;
    end;
    s := 0;
    for t:=0 to 3 do if (data[a[x,y]] and (1 shl t)) <> 0 then s := s + t;
    nh := s - (h + 2) mod 4;
    if a[x,y]='+' then nh := h;
    go( x + dx[nh], y + dy[nh], nh);            
end;

begin
    data['|'] := 1 or 4;
    data['-'] := 2 or 8;
    data['+'] := 1 or 2 or 4 or 8;
    data['1'] := 2 or 4;
    data['2'] := 1 or 2;
    data['3'] := 1 or 8;
    data['4'] := 4 or 8;

    readln(m,n);
    for i:=1 to m do
    begin
        readln(a[i]);
        move(a[i][0], a[i][1], 50);
    end;
    for i:=1 to m do
        for j:=1 to n do
            if (a[i,j]='M') or (a[i,j]='Z') then
            begin
                ok := false;
                for h:=0 to 3 do
                begin
                    x := i + dx[h];
                    y := j + dy[h];
                    if inside(x,y) and (a[x,y]<>'.') and ((data[a[x,y]] and (1 shl ((h+2) mod 4)))<>0)then
                    begin
                        ok := true;
                        go(x,y,h);
                    end;
                end;
                if not ok then
                begin
                    for h:=0 to 3 do
                    begin
                        x := i + dx[h];
                        y := j + dy[h];
                        if inside(x,y) and (a[x,y]='.') then mark[x,y] := mark[x,y] or (1 shl ((h+2) mod 4));
                    end;
                end;
            end;
    for i:=1 to m do
        for j:=1 to n do
            for z:=0 to 6 do
                if mark[i,j] = data[s[z]] then
                begin
                    ok := false;
                    for h:=0 to 3 do if (mark[i,j] and (1 shl h)) = 0 then
                    begin
                        x := i + dx[h];
                        y := j + dy[h];
                        if inside(x,y) and (not (a[x,y] in ['Z','M','.'])) and ((data[a[x,y]] and (1 shl((h+2) mod 4)))<>0) then
                            ok := true;
                    end;
                    if ok then writeln(i,#32,j,#32,'+')
                    else writeln(i,#32,j,#32,s[z]);
                    exit;
                end;
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.