[2018 SCPC 본선]
주사위
주사위의 전개도는 <그림 1>과 같다.
일반적인 주사위에서는 마주보는 두 면의 눈의 합은 항상 7이지만 본 문제에서는 주사위의 전개도에 대한 정보가 주어지기 때문에 그 성질이 만족되지 않을 수도 있다.
<그림 1>에서 보인 전개도에 대응하는 주사위를 입체적으로 나타내면 <그림 2>와 같다.
주사위가 평면에 어떻게 놓이는가에 따라 전면에서 본 값과 위에서 본 값이 다르다.
평면에 놓인 주사위를 전면에서 봤을 때 \(a\), 위에서 봤을 때 \(b\)가 보인다면 “주사위는 자세 \([a,b]\)로 놓여있다”라고 말한다.
참고로, <그림 2>에서 보인 주사위는 자세 [1,3]으로 놓여있다.
평면에 \(N×M\) 격자가 있다. <그림 3>은 \(2×M\) 격자를 보여준다.
각 칸의 좌표는 그림에서 표시한 것과 같으며, 각 칸의 크기는 주사위 한 면의 크기와 같아서, 주사위가 어떤 칸에 놓이게 되면 그 칸은 완전히 덮이게 된다.
<그림 4>는 격자 (1,1) 자리에 자세 [1,3]으로 놓인 주사위의 상태를 보여준다.
어떤 격자 칸에 놓인 주사위를 이웃한 칸으로 이동할 때는 반드시 주사위를 해당 방향으로 굴려서 이동해야 한다. <그림 5>는 <그림 4>에서 보인 주사위를 우측으로 한 번 굴려 이동한 상황을 보여주고, <그림 6>은 <그림 4>에서 보인 주사위를 아래로 한 번 굴려 이동한 상황을 보여준다. 주사위는 \(N×M\) 격자 내에서 어떤 방향으로나 굴려 이동할 수 있지만 격자 밖으로는 나갈 수는 없다.
참고로, <그림 4>에서 보인 것처럼 (1,1) 자리에 자세 [1,3] 으로 놓인 주사위를 굴려서 (1,1) → (1,2) → (2,2) → (2,1) → (1,1)로 이동하면 자세가 [4,5]로 바뀌게 되고,
(1,1) → (2,1) → (2,2) → (1,2) → (1,1)로 이동하면 자세가 [2,6] 이 된다.
주사위 전개도에 대한 정보와 네 정수 \(a, b, c, d\) 가 주어질 때,
격자 (1,1)자리에 자세 \([a,b]\)로 놓인 주사위를 격자 내에서 이리저리 굴려 격자 \(N×M\) 자리에 자세 \([c,d]\)로 놓을 수 있는지를 판단하는 프로그램을 작성하고자 한다.
만약 그렇게 할 수 있다면 주사위를 최소 몇 번 굴려야 하는지 그 횟수를 보이고, 그렇지 않다면 –1을 출력하는 프로그램을 작성하라.
주사위의 전개도를 <그림 7>과 같이 표시할 때, \(A,B,…F\) 에 대응하는 값으로 주사위의 정보를 표시한다. 각 값은 1~6 사이의 정수이다.
- 제한시간: 전체 테스트 케이스는 30개 이하이며, 전체 수행 시간은 1초 이내. (Java 1초 이내)
제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.
※ 언어별 기본 제공 소스코드 내용 참고
만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.
- 메모리 사용 제한: heap, global, static 총계 256MB, stack 1MB
입력
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. (\(1 ≤ T ≤ 30\))
각 테스트케이스에 대해 \(A\), \(B\) , \(C\) , \(D\) , \(E\) , \(F\) , \(N(1≤N≤2)\), \(M(1≤M≤100)\) , \(a\), \(b\), \(c\), \(d\) 가 한 줄에 주어진다.
여기서, \(A\)~\(F\)는 주사위 전개도 정보를 위한 수로서 1과 6사이의 서로 다른 정수이며,
\(N\)은 격자의 줄 수, \(M\)은 격자의 칸 수를 나타내는 정수이고, \(a\)~\(d\)는 주사위의 시작 자세와 마지막 자세를 나타내기 위한 정수이다.
- 점수 : 각 제출에서 취득한 점수 중에서 최대 점수 (만점 100점)
주어지는 테스트 케이스 데이터들의 그룹은 아래와 같으며,
각 그룹의 테스트 케이스를 모두 맞추었을 때 해당되는 부분 점수를 받을 수 있다.
ㆍ 그룹 1 (27점) : 이 그룹의 테스트 케이스에서는 \(N=1\)이다.
ㆍ 그룹 2 (73점) : 이 그룹의 테스트 케이스에서는 원래의 조건 외에는 다른 제약조건이 없다.
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 \(C\)는 테스트 케이스의 번호이다.
그 다음 줄에는 한 정수 값을 출력하되,
주어진 주사위에 대해, 격자 (1,1)자리에 자세 [\(a,b\)]로 놓인 것을 격자 내에서 이리저리 굴려 격자 (\(N,M\))자리에 자세 \([c,d]\)로 놓을 수 있다면
주사위를 최소 몇 번 굴려야 하는지 그 최소 횟수를 보이고, 격자 (\(N,M\))자리에 자세 \([c,d]\)로 놓는 것이 불가능하다면 –1을 출력하시오.
입출력예
| 입력 |
|---|
| 2 4 1 3 5 6 2 1 3 1 3 1 4 4 1 3 5 6 2 2 3 1 3 1 4 |
| 출력 |
|---|
| Case #1 2 Case #2 -1 |