cho.sh4 × 4 토러스 퍼즐
4 by 4 토러스 격자에서 행과 열을 순환 이동해 주어진 색 배치를 목표 배치로 만드는 최소 이동 횟수를 구합니다.
어려움8BFS그래프완전 탐색아직 제출이 없습니다시간 제한5초메모리 제한256 MB문제 설명
예제2
문제
색칠된 칸이 4 × 4 격자로 놓인 퍼즐이 있다. 각 칸의 색은 빨강(R), 초록(G), 파랑(B), 노랑(Y) 중 하나이고, 네 색이 각각 정확히 네 번씩 나온다.
완성된 상태는 다음 배치 하나뿐이다.
RRRR
GGGG
BBBB
YYYY
이 배치만 완성으로 인정한다. 위에서부터 GGGG, BBBB, YYYY, RRRR로 놓인 상태는 색이 행마다 하나씩이지만 완성이 아니다.
격자는 평면이 아니라 토러스(가운데에 구멍이 뚫린 도넛) 위에 씌워져 있다. 맨 위 행과 맨 아래 행이 이어져 있고, 맨 왼쪽 열과 맨 오른쪽 열도 이어져 있다.
한 번의 이동으로 한 행을 왼쪽이나 오른쪽으로 한 칸 밀거나, 한 열을 위나 아래로 한 칸 밀 수 있다. 격자 밖으로 밀려난 칸은 반대편 끝에 다시 나타난다.
아래 그림은 어떤 상태를 세 번의 이동으로 완성하는 과정이다.
퍼즐의 상태가 주어질 때, 완성하는 데 필요한 최소 이동 횟수를 구하라. 어떤 상태든 13번 미만의 이동으로 완성할 수 있다.
입력
입력은 정확히 네 줄이고, 각 줄은 R, G, B, Y 중 네 글자로 이루어진다. 입력은 이 퍼즐에서 실제로 나올 수 있는 상태이므로 네 색이 각각 정확히 네 번씩 나온다.
출력
완성하는 데 필요한 최소 이동 횟수를 한 줄에 출력한다.