주사위 대회

시간 제한1초메모리 제한128 MB

요약
면에 숫자가 적힌 주사위를 4행짜리 무한 띠 위에서 굴려 시작 칸에서 목표 칸까지 이동시킬 때, 방향 상태를 추적하며 총 비용을 최소화하는 문제입니다.
난이도

보통10점 중 7점

유형
최단 경로, BFS, 시뮬레이션
정답자
아직 제출이 없습니다

문제

한 마을에서는 매주 주사위 대회가 열린다. 예전에는 1부터 6까지의 눈이 그려진 평범한 육면체 주사위로 놀았지만 곧 시들해졌고, 요즘에는 여섯 면에 각각 양의 정수가 적힌 스티커를 붙인 주사위를 사용한다.

대회는 체스판처럼 정사각형 칸으로 나뉜 띠 위에서 진행된다. 띠는 세로로 4칸이고 좌우로 무한히 뻗어 있다. 행은 아래에서 위로 1부터 4까지 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 갈수록 커지는 연속된 정수로 번호가 매겨진다. 각 칸은 열 번호 xx와 행 번호 yy의 쌍 (x,y)(x, y)로 나타낸다.

처음에 주사위는 선택된 칸 위에 1의 눈이 위를 향하고 2의 눈이 참가자 쪽을 향하도록 놓인다. 한 번의 이동은 주사위를 아래쪽 모서리 중 하나를 축으로 굴려 상하좌우로 인접한 칸으로 옮기는 것이다. 이동 비용은 굴린 뒤 맨 위에 오는 면에 적힌 정수이다. 목표는 시작 칸에서 도착 칸까지 주사위를 굴려 옮기되 모든 이동 비용의 합을 최소로 만드는 것이다. 평범한 주사위와 마찬가지로 마주 보는 두 면의 원래 눈의 합은 7이다.

주사위에 적힌 수와 시작 칸, 도착 칸이 주어질 때 가능한 최소 총비용을 출력하여라.

입력

첫째 줄에 여섯 정수 l1,l2,l3,l4,l5,l6l_1, l_2, l_3, l_4, l_5, l_6 (1≤li≤501 \le l_i \le 50)이 주어진다. lil_i는 원래 눈이 ii개였던 면에 적힌 수이다.

둘째 줄에 네 정수 x1,y1,x2,y2x_1, y_1, x_2, y_2 (−109≤x1,x2≤109-10^9 \le x_1, x_2 \le 10^9, 1≤y1,y2≤41 \le y_1, y_2 \le 4)가 주어진다. (x1,y1)(x_1, y_1)은 시작 칸, (x2,y2)(x_2, y_2)는 도착 칸이다.

출력

시작 칸에서 도착 칸까지 주사위를 굴려 옮기는 최소 총비용을 한 줄에 출력한다.

예제6

  1. 예제 1

    입력
    1 2 3 8 1 4
    -1 1 0 2
    
    예상 출력
    5
    
  2. 예제 2

    입력
    1 2 3 4 5 6
    5 3 5 3
    
    예상 출력
    0
    
  3. 예제 3

    입력
    1 2 3 4 5 6
    0 1 0 4
    
    예상 출력
    13
    
  4. 예제 4

    입력
    5 4 3 2 1 6
    0 1 3 1
    
    예상 출력
    11
    
  5. 예제 5

    입력
    2 9 4 7 1 5
    5 2 1 2
    
    예상 출력
    18
    
  6. 예제 6

    입력
    2 40 3 41 5 42
    -50 1 50 4
    
    예상 출력
    2248