시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 486 303 270 68.182%

문제

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
W3sicHJvYmxlbV9pZCI6IjMwNDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOLVx1ZDM3Y1x1Yzk5MCIsImRlc2NyaXB0aW9uIjoiPHA+Ti1cdWQzN2NcdWM5OTBcdWM3NDAgXHViOWNlXHVjNzQwIFx1YjJlNFx1YzU5MVx1ZDU1YyBcdWQ2MTVcdWQwZGNcdWM2NDAgXHVjNzc0XHViOTg0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViYzg4IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjMGI0XHVkM2I0XHViY2ZjIFx1YWM4M1x1Yzc0MCAxNS1cdWQzN2NcdWM5OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+MTUtXHVkMzdjXHVjOTkwXHVjNzQwIDQqNFx1YmNmNFx1YjRkY1x1YzVkMFx1YzExYyBcdWM2YzBcdWM5YzFcdWM3N2MgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVkNTVjIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWJlNjBcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBBXHViZDgwXHVkMTMwIE9cdWFlNGNcdWM5YzAgXHVjNzc0XHViOTg0XHVjNzc0IFx1YmQ5OVx1YzVlY1x1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDgwXHViYTc0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGY4XHViOWJjXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuXHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MTAwcHhcIj5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5BPFwvdGQ+XHJcblx0XHRcdDx0ZD5CPFwvdGQ+XHJcblx0XHRcdDx0ZD5DPFwvdGQ+XHJcblx0XHRcdDx0ZD5EPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPkU8XC90ZD5cclxuXHRcdFx0PHRkPkY8XC90ZD5cclxuXHRcdFx0PHRkPkc8XC90ZD5cclxuXHRcdFx0PHRkPkg8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+STxcL3RkPlxyXG5cdFx0XHQ8dGQ+SjxcL3RkPlxyXG5cdFx0XHQ8dGQ+SzxcL3RkPlxyXG5cdFx0XHQ8dGQ+TDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5NPFwvdGQ+XHJcblx0XHRcdDx0ZD5OPFwvdGQ+XHJcblx0XHRcdDx0ZD5PPFwvdGQ+XHJcblx0XHRcdDx0ZD4uPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgMTUtXHVkMzdjXHVjOTkwXHVjNWQwXHVjMTFjIFx1ZDc2OVx1YzViNFx1YzlkMCBcdWM4MTVcdWIzYzRcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDc2OVx1YzViNFx1YzlkMCBcdWM4MTVcdWIzYzRcdWIyOTQgXHVhYzAxIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQ2MDRcdWM3YWMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ0ODBcdWM1YzhcdWM3NDQgXHViNTRjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YjQ1MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1YWRmOCBcdWI0NTAgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWI5ZThcdWQ1NzRcdWQyYmMgXHVhYzcwXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPjE1LVx1ZDM3Y1x1Yzk5MFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQ3NjlcdWM1YjRcdWM5ZDAgXHVjODE1XHViM2M0XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+NFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVkNjA0XHVjN2FjIFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWQ3NjlcdWM1YjRcdWM5ZDAgXHVjODE1XHViM2M0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTlBVWlpMRSIsImRlc2NyaXB0aW9uIjoiPHA+Ti1wdXp6bGUgaXMgYSBwdXp6bGUgdGhhdCBnb2VzIGJ5IG1hbnkgbmFtZXMgYW5kIGhhcyBtYW55IHZhcmlhbnRzLiBJbiB0aGlzIHByb2JsZW0gd2Ugd2lsbCB1c2UgdGhlIDE1LXB1enpsZS4gSXQgY29uc2lzdHMgb2YgYSA0LWJ5LTQgZ3JpZCBvZiBzbGlkaW5nIHNxdWFyZXMgd2hlcmUgb25lIHNxdWFyZSBpcyBtaXNzaW5nLiBUaGUgc3F1YXJlcyBhcmUgbGFiZWxlZCB3aXRoIHVwcGVyY2FzZSBsZXR0ZXJzICYjMzk7QSYjMzk7IHRocm91Z2ggJiMzOTtPJiMzOTssIHdpdGggdGhlIGRlc2lyZWQgbGF5b3V0IGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCIgc3R5bGU9XCJ3aWR0aDoxMDBweFwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPkE8XC90ZD5cclxuXHRcdFx0PHRkPkI8XC90ZD5cclxuXHRcdFx0PHRkPkM8XC90ZD5cclxuXHRcdFx0PHRkPkQ8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+RTxcL3RkPlxyXG5cdFx0XHQ8dGQ+RjxcL3RkPlxyXG5cdFx0XHQ8dGQ+RzxcL3RkPlxyXG5cdFx0XHQ8dGQ+SDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5JPFwvdGQ+XHJcblx0XHRcdDx0ZD5KPFwvdGQ+XHJcblx0XHRcdDx0ZD5LPFwvdGQ+XHJcblx0XHRcdDx0ZD5MPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPk08XC90ZD5cclxuXHRcdFx0PHRkPk48XC90ZD5cclxuXHRcdFx0PHRkPk88XC90ZD5cclxuXHRcdFx0PHRkPi48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcblxyXG48cD5JdCBjYW4gYmUgdXNlZnVsIChmb3IgZXhhbXBsZSwgd2hlbiBzb2x2aW5nIHRoZSBwdXp6bGUgdXNpbmcgYSBjb21wdXRlcikgdG8gZGVmaW5lIHRoZSAmcXVvdDtzY2F0dGVyJnF1b3Q7IG9mIGEgcHV6emxlIGFzIHRoZSBzdW0gb2YgZGlzdGFuY2VzIGJldHdlZW4gZWFjaCBzcXVhcmUmIzM5O3MgY3VycmVudCBwb3NpdGlvbiBhbmQgaXRzIHBvc2l0aW9uIGluIHRoZSBkZXNpcmVkIGxheW91dC4gVGhlIGRpc3RhbmNlIGJldHdlZW4gdHdvIHNxdWFyZXMgaXMgdGhlaXIgTWFuaGF0dGFuIGRpc3RhbmNlICh0aGUgYWJzb2x1dGUgdmFsdWUgb2YgdGhlIHN1bSBvZiBkaWZmZXJlbmNlcyBiZXR3ZWVuIHRoZSB0d28gcm93cyBhbmQgdGhlIHR3byBjb2x1bW5zKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgc2NhdHRlciBvZiB0aGUgZ2l2ZW4gcHV6emxlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rm91ciBsaW5lcyBvZiBpbnB1dCBjb250YWluIGZvdXIgY2hhcmFjdGVycyBlYWNoLCByZXByZXNlbnRpbmcgdGhlIHN0YXRlIG9mIHRoZSBwdXp6bGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgc2NhdHRlciBvZiB0aGUgcHV6emxlIG9uIGEgc2luZ2xlIGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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