ai giai gup minh bai nay cai

[hoatink4]

Bài Hành trình rẻ nhất:
Thành phố Peace vừa đưa vào áp dụng một hệ thống điện tử tự động tính lệ phí sử dụng lệ phí đường giao thông. Một hệ thống được triển khai để phát hiện xe của bạn rẽ trái, rẽ phải, đi thẳng hoặc quay đầu và mỗi thao tác như vậy phải trả một lệ phí tương ứng. Đó là 1 $ cho mỗi lần rẽ trái, 5$ cho mỗi lần rẽ phải, đi thẳng về phía trước là miễn phí, quay đầu xe là bị cấm, ngoại trừ tình huống ở cuối phố khi không còn có thể đi thẳng, rẽ trái, hoặc rẽ phải được nữa. Trong trường hợp ngoại lệ bắt buộc phải quay đầu xe, bạn phải trả lệ phí 10$. Bạn được mời để thiết kế và đưa ra chỉ dẫn cho người đi xe đi sao cho phải trả lệ phí là ít nhất giữa 2 điểm bất kỳ trong thành phố. Rất may hệ thống đường giao thông của Peace có dạng bàn cờ.
Ví dụ:
input
8 11
. . . . . . . . . . .
. . . . # # # # # . .
. . . . # . . . # . .
. . . . # . . . # . .
. # E # # # # # # . .
. . . . # . . . . . .
. # # F # . . . . . .
. . . . . . . . . . .

output:8
ở ví dụ trên ký tự ’#’ để chỉ ra đoạn đường phố, còn ký tự ’.’ chỉ ra đoạn đường không là đường. Các đoạn đường phố đều có thể đi cả 2 chiều. Ký tự ’E’ chỉ ra vị trí xuất phát của xe ô tô có đầu xe hướng về phía Đông, còn ký tự ’F’ chỉ ra vị trí kết thúc. Lộ trình phải trả là 8$, trong đó ta phải thực hiên 3 lần rẽ trái và 1 lần rẽ phải để đến đích. Ta có thể thực hiện cách đi rẽ phải 2 lần đễ đến đích, nhưng cách đó lệ phí phải trả là 10$.

Chiều cao và chiều rộng của bản đồ ít nhất là 4 và không quá 30. Bản đồ có đúng 1 điểm xuất phát và 1 điểm kết thúc. Luôn có đường đi từ điểm xuất phát đến điểm kết thúc. Luôn có một khung gồm toàn ký tự ’.’ viền bản đồ để không thể vượt ra ngoài bản đồ.
Dữ liệu: Vào từ file văn bản ERP.INP gồm các dòng:
- Dòng thứ nhất chứa 2 số nguyên dương h, w theo thứ tự là chiều cao h và chiều rộng của bản đồ.
- Mỗi dòng trong h dòng tiếp theo chứa w ký tự. Mỗi ký tự chỉ là một trong số các ký tự sau:
- ’.’: vị trí không có đường
- ’#’: vị trí có đường của bản đồ.
- ’E’: vị trí xuất phát, xe hướng đầu về phía Đông.
- ’W’: vị trí xuất phát, xe hướng đầu về phía Tây.
- ’N’: vị trí xuất phát, xe hướng đầu về phía Bắc.
- ’S’: vị trí xuất phát, xe hướng đầu về phía Nam.
- ’F’: vị trí kết thúc.
Trong bản đồ có đúng 1 trong 4 ký tự ’E’, ’W’, ’N’, ’S’. Và đúng 1 ký tự F.
Kết quả ghi ra file văn bản ERP.OUT duy nhất một số là lệ phí của lộ trình rẻ nhất đi từ vị trí xuất phát đến vị trí kết thúc.

[MMKC_IT]

Way lui, chiều rộng, tạo thành đường đi rồi giải theo dijkstra.
Khôn bít QHD được không??

[mr_invincible]

Xét đồ thị với mỗi đỉnh gồm: tọa độ ô (hàng, cột) và hướng đi vào ô (4 hướng). dijkstra. Dạng bài này hình như không quy hoạch động được

[hoatink4]

mình đã cài rồi nhưng vẩn không được
các bạn cài giúp mình chương trình luôn cái

[=========> Bổ sung bài viết <=========]

bài này khi dùng quay lui nhửng ô đã đi qua vẩn có thể nên quay trơ lại
tọa thành vòng luẩn quẩn

[chopes]

Bài này mình cài như sau mọi ngừoi xem rồi góp ý hộ mình cái

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.

[thuonghcm]

hic bạn không viết trong {[code]} ai mà đọc cho nổi
nhức mắt quá, cho thuật toán cụ thể đi

[=========> Bổ sung bài viết <=========]

mình thấy choáng quá nên cũng copy về dán và..chạy thử....hic
KQ= 1000 ?

[chopes]

bài này mình dùng thuật toán dijkstra theo đủ 4 hướng đông tây nam bắc . Chạy với bọ test ở trên đuọc kết quả đúng là 8

[hoatink4]

mình đã copy và chạy thử nhưng kết quả khác
bạn coi lại giùm

[chopes]

chạy trong Free đựoc kết quả đúng với lại xem lại file inp với, làm sao mà đọc cho đúng input là đựoc

[mr_invincible]

mình đã cài rồi nhưng vẩn không được
các bạn cài giúp mình chương trình luôn cái

[=========> Bổ sung bài viết <=========]

bài này khi dùng quay lui nhửng ô đã đi qua vẩn có thể nên quay trơ lại
tọa thành vòng luẩn quẩn

Bạn phải cài nhiều và cố gắng tự tìm chỗ sai của mình thì mới giỏi lên được. Nhờ người khác code hộ chẳng có ý nghĩa gì cả :|