Code:
Const fi='erp.inp';
fo='erp.out';
maxa=1000;
Var c:array[1..31,1..31,1..4]of integer;
a:array[1..31,1..31]of char;
boo:array[1..31,1..31,1..4]of boolean;
f:text;
m,n,dx,dy,xpx,xpy:integer;
Procedure doc;
Var i,j,t:integer;xp,d:boolean;
Begin
Assign(f,fi);reset(f);
Fillchar(boo,sizeof(boo),true);
Readln(f,m,n);
For i:=1 to m do
Begin
For j:=1 to n do
Begin
read(f,a[i,j]);
If a[i,j]='.' then
For t:=1 to 4 do boo[i,j,t]:=false
Else If (xp)or(d) then
If a[i,j]='F' then Begin dx:=i;dy:=j;d:=false;End
Else If a[i,j]<>'#' then Begin xpx:=i;xpy:=j;xp:=false;End;
For t:=1 to 4 do
c[i,j,t]:=maxa;
End;
readln(f);
End;
End;
Function huong(i,j,u,v:integer):integer;
Var x,y:integer;h2:integer;
Begin
x:=i-u;y:=j-v;
If (x=0)and(abs(y)=1)then
If y=1 then h2:=2
Else h2:=1
Else If (y=0)and(abs(x)=1) then
If x=1 then h2:=4
Else h2:=3
Else h2:=maxa;
huong:=h2;
End;
Function cost(i,j,h1,u,v,h2:integer):integer;
Var x,y,d,dem:integer;
Begin
If (h1=h2) then d:=0
Else
If ((h1=4)and(h2=1))or ((h1=1)and(h2=3))or
((h1=3)and(h2=2))or((h1=2)and(h2=4)) then d:=5
Else If ((h1=1)and(h2=4))or((h1=4)and(h2=2))or
((h1=2)and(h2=3))or((h1=3)and(h2=1)) then d:=1
Else Begin
dem:=0;
If a[i,j+1]='.' then dem:=dem+1;
If a[i+1,j]='.' then dem:=dem+1;
If a[i,j-1]='.' then dem:=dem+1;
If a[i-1,j]='.' then dem:=dem+1;
If dem=3 then d:=10 else d:=maxa;
End;
cost:=d;
End;
Procedure dijkstra;
Var ktr:boolean;ui,uj,ut,i,j,t,k,gt,min,dem,th:integer;
Begin
If a[xpx,xpy]='E' then c[xpx,xpy,1]:=0
Else If a[xpx,xpy]='W' then c[xpx,xpy,2]:=0
Else If a[xpx,xpy]='S' then c[xpx,xpy,3]:=0
Else If a[xpx,xpy]='N' then c[xpx,xpy,4]:=0;
th:=0;
If a[dx,dy+1]='#' then th:=th+1;
If a[dx,dy-1]='#' then th:=th+1;
If a[dx+1,dy]='#' then th:=th+1;
If a[dx-1,dy]='#' then th:=th+1;
dem:=0;
Repeat
ui:=0;min:=maxa;
For i:=1 to m do
For j:=1 to n do
For t:=1 to 4 do
If boo[i,j,t] then
If c[i,j,t]<min then
Begin
min:=c[i,j,t];
ui:=i;uj:=j;ut:=t;
End;
If (ui=dx)and(uj=dy)then dem:=dem+1;
If (ui=0)or (dem=th) then break;
boo[ui,uj,ut]:=false;
For i:=1 to m do
For j:=1 to n do
Begin
t:=huong(ui,uj,i,j);
If t<>maxa then
If boo[i,j,t] then
Begin
gt:=cost(ui,uj,ut,i,j,t);
If c[i,j,t]>(min+gt) then
c[i,j,t]:=min+gt;
End;
End;
Until dem=th;
End;
Procedure ghi;
Var min,i:integer;
Begin
Assign(f,fo);rewrite(f);
min:=c[dx,dy,1];
For i:=2 to 4 do
If c[dx,dy,i]<min then min:=c[dx,dy,i];
Writeln(f,min);
Close(f);
End;
Begin
doc;
dijkstra;
ghi;
End.
Bookmarks