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

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
If a[i,j] <> '.' then inc(brnum);
End;
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;

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