시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1461 | 960 | 852 | 70.588% |
N-퍼즐은 많은 다양한 형태와 이름이 있다. 이번 문제에서 우리가 살펴볼 것은 15-퍼즐이다.
15-퍼즐은 4*4보드에서 움직일 수 있는 정사각형으로 이루어져 있고, 한 정사각형은 빠져있다. 정사각형은 A부터 O까지 이름이 붙여져 있다. 이 퍼즐을 풀면 다음과 같은 그림이 된다.
A | B | C | D |
E | F | G | H |
I | J | K | L |
M | N | O | . |
우리는 이러한 15-퍼즐에서 흩어짐 정도를 계산할 수 있다. 흩어짐 정도는 각 정사각형의 현재 위치와 퍼즐을 풀었을 때의 위치와의 거리의 합이다.
두 정사각형의 거리는 그 두 정사각형 사이의 맨해튼 거리이다.
15-퍼즐이 주어졌을 때, 흩어짐 정도를 계산하는 프로그램을 작성하시오.
4줄에 걸쳐 현재 퍼즐의 상태가 주어진다.
퍼즐의 흩어짐 정도를 출력한다.
ABCD EFGH IJKL M.NO
2
.BCD EAGH IJFL MNOK
6
Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 2번