Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

XUCXAC - Xúc xắc

Một mặt bàn nằm ngang được chia làm lưới ô vuông, trong mỗi ô có ghi một số tự nhiên.

Cho 1 con xúc xắc nằm vừa vặn trên một ô của lưới. Mỗi mặt của xúc xắc là một số từ 1 đến 6. Ban đầu, mặt trước là số 1, mặt trên là số 2 và mặt bên phải là số 3, các mặt đối diện có tổng số là 7. Mỗi lần, con xúc xắc có thể lăn về phía trái, phải, trước, sau. Mỗi lần tiếp xúc với mặt bàn, ta mất một chi phí bằng số ghi trên ô mà xúc xắc đang nằm trên nhân với số trên mặt của xúc xắc đang tiếp xúc với mặt bàn.

Hãy tìm cách lăn từ một ô đến một ô khác trên mặt bàn để đạt chi phí nhỏ nhất.

Dữ liệu

  • Dòng đầu ghi 2 số M, N lần lượt là số dòng và số cột của lưới ô trên mặt bàn.
  • M dòng sau, mỗi dòng ghi N số nguyên không quá 100 là số ghi trên các ô lưới của mặt bàn. Các dòng được liệt kê theo thứ tự từ xa đến gần, các số trên mỗi dòng liệt kê từ trái sang phải.
  • Dòng cuối ghi 2 cặp số lần lượt là tọa độ (dòng, cột) của ô bắt đầu và ô kết thúc.

Kết quả

Ghi ra một số duy nhất là chi phí nhỏ nhất tìm được.

Giới hạn

1 ≤ M,N ≤ 50.

Ví dụ

Dữ liệu
3 3
1 2 3
4 5 6
7 8 9
2 2 3 3

Kết quả
52


Được gửi lên bởi:VOJ problem setters
Ngày:2008-06-07
Thời gian chạy:0.122s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Khúc Anh Tuấn

hide comments
2013-11-06 10:35:03 Phạm Bá Thái
đưa về đồ thị 24*n*m thôi bạn à
2013-10-31 16:15:34 Chuyên Triết Tổng Hợp
clq nhưng hôm nay là halloween
2013-08-31 14:16:19 dũng
test de bai co cach di ntn vay?
2012-07-30 09:30:42 Erik
Tạo đồ thị mới, mỗi đỉnh có 5 chỉ số
hàng, cột, số xúc xắc ở trên, mặt trước là mặt phải

=> đồ thị 50 * 50 * 6 * 6 * 6

Cuối cùng là dijsktra trên đồ thị mới :)

Sol 0.3s :)

Last edit: 2012-07-30 09:31:47
2011-09-01 15:20:35 ‮ ‮
Trái phải là ntn hả PS, sang trái là 4 hay 6

Last edit: 2011-09-01 15:22:37
2010-03-26 14:19:05 lee
very good
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.