Một bài đồ thị hay. Mời mọi người thử sức !

[[T][a][r][a]]

Cho một mạng lưới mảng 2 chiều, mỗi ô ghi 1 số tự nhiên. Cho 1 xúc xắc đặt ngẫu nhiên tại 1 trong những ô bất kì trên mảng 2 chiều đó. Vị trí ban đầu mà xúc xắc đặt như sau: mặt dưới 5 , mặt trước 1, mặt sau 6, mặt trên 2, mặt phải 3, mặt trái 4 . Chi phí để 1 ô xúc xăc đi từ ô này đến ô kia được tính bằng tích của số tự nhiên của ô mà xúc xắc đang được đặt với số ghi trên xúc xắc ở mặt tiếp xúc với ô đó ( tức là mặt dưới của xúc xắc í ). Mỗi lần di chuyển từ ô này đến ô kia, xúc xắc chỉ được di chuyển trên, xuống, trái, phải ( ko được di chuyển chéo ) . Yêu cầu đặt ra là từ ô ban đầu (i,j); hãy tìm ra chi phí nhỏ nhất để xúc xắc đi đến ô (x,y).
File INP : dòng đầu ghi kích thước của mảng 2 chiều
các dòng sau mô tả mảng 2 chiều đó
dòng cuối cùng ghi 4 kí tự số : 2 kí tự đầu là tọa độ của ô ban đầu, 2 kí tự tiếp theo là tọa độ của ô kết thúc
File OUT: ghi ra số là chi phí của con đường ngắn nhất để xúc xắc đi từ ô đầu đến ô cuối
Ví dụ :
INP
3 3
1 2 3
4 5 6
7 8 9
2 2 3 3
OUT
52

Giải thích: mảng lúc đầu có 3 dòng, 3 cột, 3 dòng tiếp theo mô tả mảng 2 chiều đó . Yêu cầu đi từ ô (2.2) -> (3.3) . Lộ trình của xúc xắc sẽ là (2.2) - > (2.3) -> (3.3). Khi ở ô (2.2), chi phí của xúc xắc là 5*5 (số của ô đang chứa xúc xắc với mặt dưới của xúc xắc là 5 như đề đã cho) ; đến ô (3.2) mặt dưới của xúc xắc lúc này sẽ là 3 => chi phí là 6*3; đến ô (3.3) , tương tự, chi phí là 9*1 => Tổng chi phí là 5*5 + 6*3 + 9*1 = 52

*************** Viết bằng Pascal nhé mí bạn :D

[HGMinh95]

Bạn có thể nói rõ giới hạn của mảng 2 chiều ko.

[[T][a][r][a]]

A, chào bạn Minh, mình có add nick bạn nè ^^. Bạn cứ cho giới hạn nhỏ thôi coi chạy đc chưa đã

[HGMinh95]

[a][r][a];3311711']A, chào bạn Minh, mình có add nick bạn nè ^^. Bạn cứ cho giới hạn nhỏ thôi coi chạy đc chưa đã
Bạn add nick nào của mình vậy ???

Nếu nhỏ chắc quay lui + nhánh cận là ra.

[[T][a][r][a]]

Bạn có thể nói rõ cho mình đc ko ?

[HGMinh95]

Đây là mã giả


procedure init;
begin
bestconfig = max;
end;

procedure Attempt(k);
begin
for <mọi ô có thể đi được từ ô k> do
begin
<Ghi nhận việc thử cho ô k+1>
if <tổng chi phí đi từ ô xuất phát đến ô k+1 < bestconfig> then
if <đã đến đích> then <cập nhật bestconfig>
else
begin
Attempt(k+1);
<Bỏ ghi nhận việc thử>
end;
end;
end;

[haplinhavxt]

Bài này như này ko thể ăn được, cách giải tối ưu là dùng thuật toán dijkstra trên mảng 4 chiều!

[HGMinh95]

Bạn nói rõ hơn được ko?

[haplinhavxt]

Ta lập 1 đồ thì mới, mỗi đỉnh có 4 trạng thái( ô tiếp xúc, đỉnh bên trái, đỉnh đằng trước, và đang ở ô nào), mỗi trạng thái này sẽ tương ứng các trạng thái ở các ô cạnh nó, ta sẽ ijk trên cái đồ thị mới này!