시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 982 601 544 68.085%

문제

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줄에 걸쳐 현재 퍼즐의 상태가 주어진다.

출력

퍼즐의 흩어짐 정도를 출력한다.

예제 입력 1

ABCD
EFGH
IJKL
M.NO

예제 출력 1

2

예제 입력 2

.BCD
EAGH
IJFL
MNOK

예제 출력 2

6
W3sicHJvYmxlbV9pZCI6IjMwNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOLVx1ZDM3Y1x1Yzk5MCIsImRlc2NyaXB0aW9uIjoiPHA+Ti1cdWQzN2NcdWM5OTBcdWM3NDAgXHViOWNlXHVjNzQwIFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWQ2MTVcdWQwZGNcdWM2NDAgXHVjNzc0XHViOTg0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViYzg4IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjMGI0XHVkM2I0XHViY2ZjIFx1YWM4M1x1Yzc0MCAxNS1cdWQzN2NcdWM5OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjE1LVx1ZDM3Y1x1Yzk5MFx1Yzc0MCA0KjRcdWJjZjRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1ZDU1YyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHViZTYwXHVjODM4XHVjNzg4XHViMmU0LiBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgQVx1YmQ4MFx1ZDEzMCBPXHVhZTRjXHVjOWMwIFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWJkOTlcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkMzdjXHVjOTkwXHVjNzQ0IFx1ZDQ4MFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWRmOFx1YjliY1x1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoxMDBweFwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPkE8XC90ZD5cclxuXHRcdFx0PHRkPkI8XC90ZD5cclxuXHRcdFx0PHRkPkM8XC90ZD5cclxuXHRcdFx0PHRkPkQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+RTxcL3RkPlxyXG5cdFx0XHQ8dGQ+RjxcL3RkPlxyXG5cdFx0XHQ8dGQ+RzxcL3RkPlxyXG5cdFx0XHQ8dGQ+SDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5JPFwvdGQ+XHJcblx0XHRcdDx0ZD5KPFwvdGQ+XHJcblx0XHRcdDx0ZD5LPFwvdGQ+XHJcblx0XHRcdDx0ZD5MPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPk08XC90ZD5cclxuXHRcdFx0PHRkPk48XC90ZD5cclxuXHRcdFx0PHRkPk88XC90ZD5cclxuXHRcdFx0PHRkPi48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgMTUtXHVkMzdjXHVjOTkwXHVjNWQwXHVjMTFjIFx1ZDc2OVx1YzViNFx1YzlkMCBcdWM4MTVcdWIzYzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDc2OVx1YzViNFx1YzlkMCBcdWM4MTVcdWIzYzRcdWIyOTQgXHVhYzAxIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQ2MDRcdWM3YWMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ0ODBcdWM1YzhcdWM3NDQgXHViNTRjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCBcdWFkZjggXHViNDUwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWMwYWNcdWM3NzRcdWM3NTggXHViOWU4XHVkNTc0XHVkMmJjIFx1YWM3MFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MTUtXHVkMzdjXHVjOTkwXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDc2OVx1YzViNFx1YzlkMCBcdWM4MTVcdWIzYzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD40XHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWQ2MDRcdWM3YWMgXHVkMzdjXHVjOTkwXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMzdjXHVjOTkwXHVjNzU4IFx1ZDc2OVx1YzViNFx1YzlkMCBcdWM4MTVcdWIzYzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwNDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOUFVaWkxFIiwiZGVzY3JpcHRpb24iOiI8cD5OLXB1enpsZSBpcyBhIHB1enpsZSB0aGF0IGdvZXMgYnkgbWFueSBuYW1lcyBhbmQgaGFzIG1hbnkgdmFyaWFudHMuIEluIHRoaXMgcHJvYmxlbSB3ZSB3aWxsIHVzZSB0aGUgMTUtcHV6emxlLiBJdCBjb25zaXN0cyBvZiBhIDQtYnktNCBncmlkIG9mIHNsaWRpbmcgc3F1YXJlcyB3aGVyZSBvbmUgc3F1YXJlIGlzIG1pc3NpbmcuIFRoZSBzcXVhcmVzIGFyZSBsYWJlbGVkIHdpdGggdXBwZXJjYXNlIGxldHRlcnMgJiMzOTtBJiMzOTsgdGhyb3VnaCAmIzM5O08mIzM5Oywgd2l0aCB0aGUgZGVzaXJlZCBsYXlvdXQgYXMgZm9sbG93czombmJzcDs8XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjEwMHB4XCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+QTxcL3RkPlxyXG5cdFx0XHQ8dGQ+QjxcL3RkPlxyXG5cdFx0XHQ8dGQ+QzxcL3RkPlxyXG5cdFx0XHQ8dGQ+RDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5FPFwvdGQ+XHJcblx0XHRcdDx0ZD5GPFwvdGQ+XHJcblx0XHRcdDx0ZD5HPFwvdGQ+XHJcblx0XHRcdDx0ZD5IPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPkk8XC90ZD5cclxuXHRcdFx0PHRkPko8XC90ZD5cclxuXHRcdFx0PHRkPks8XC90ZD5cclxuXHRcdFx0PHRkPkw8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+TTxcL3RkPlxyXG5cdFx0XHQ8dGQ+TjxcL3RkPlxyXG5cdFx0XHQ8dGQ+TzxcL3RkPlxyXG5cdFx0XHQ8dGQ+LjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuXHJcbjxwPkl0IGNhbiBiZSB1c2VmdWwgKGZvciBleGFtcGxlLCB3aGVuIHNvbHZpbmcgdGhlIHB1enpsZSB1c2luZyBhIGNvbXB1dGVyKSB0byBkZWZpbmUgdGhlICZxdW90O3NjYXR0ZXImcXVvdDsgb2YgYSBwdXp6bGUgYXMgdGhlIHN1bSBvZiBkaXN0YW5jZXMgYmV0d2VlbiBlYWNoIHNxdWFyZSYjMzk7cyBjdXJyZW50IHBvc2l0aW9uIGFuZCBpdHMgcG9zaXRpb24gaW4gdGhlIGRlc2lyZWQgbGF5b3V0LiBUaGUgZGlzdGFuY2UgYmV0d2VlbiB0d28gc3F1YXJlcyBpcyB0aGVpciBNYW5oYXR0YW4gZGlzdGFuY2UgKHRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiB0aGUgc3VtIG9mIGRpZmZlcmVuY2VzIGJldHdlZW4gdGhlIHR3byByb3dzIGFuZCB0aGUgdHdvIGNvbHVtbnMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBzY2F0dGVyIG9mIHRoZSBnaXZlbiBwdXp6bGUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Gb3VyIGxpbmVzIG9mIGlucHV0IGNvbnRhaW4gZm91ciBjaGFyYWN0ZXJzIGVhY2gsIHJlcHJlc2VudGluZyB0aGUgc3RhdGUgb2YgdGhlIHB1enpsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzY2F0dGVyIG9mIHRoZSBwdXp6bGUgb24gYSBzaW5nbGUgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 2번