Xúc xắc

Xem dạng PDF

Gửi bài giải


Điểm: 0,36 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
Khúc Anh Tuấn
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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.

Input

  • 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.

Output

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

Giới hạn

~1 \leq M~, ~N \leq 50~.

Sample Input

3 3
1 2 3
4 5 6
7 8 9
2 2 3 3

Sample Output

52

Note

image


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -2
    Atlant  đã bình luận lúc 7, Tháng 5, 2021, 4:45

    cho mình hỏi trạng thái ban đầu của xúc xắc trên ô bắt đầu là như nào với


    • 1
      tiozo  đã bình luận lúc 16, Tháng 6, 2021, 8:30

      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