30396번 - 기사들의 여행

문제

최근 체스에 관심을 가지게 된 창현이와 예환이는 4×4개의 칸이 4행 4열로 이루어진 정사각형 모양의 체스판을 사기로 하였다. 하지만 창현이가 구매 옵션을 잘못 선택하는 바람에 나이트만 가득 들어있는 체스판을 구매해 버렸다! 체스의 기물 중 하나인 나이트는 한 번 이동할 때 현재 위치에서 상하좌우 중 한 방향으로 두 칸 간 후, 그것에 수직인 방향으로 꺾어서 한 칸 더 간다. 나이트가 이동한 후에는 체스판을 벗어나거나 같은 칸에 두 개 이상의 나이트가 존재해서는 안 된다.

잘못 구매한 체스판을 어떻게 처리할까 고민하던 창현이와 예환이는 나이트들이 배치된 두 개의 체스판 A, B를 그린 뒤, A의 나이트들 위치를 B처럼 만드는 데 필요한 최소 이동 횟수를 늦게 구하는 사람이 치우기로 하였다. 창현이는 치우는 게 귀찮기 때문에 꼭 이기고 싶다.

창현이를 도와 나이트들의 최소 이동 횟수를 구하는 프로그램을 만들어 보자. 나이트는 한 번에 한 개만 움직일 수 있다.

입력

체스판은 4×4개의 칸이 4행 4열로 이루어진 정사각형 모양이다. 첫 번째 줄부터 네 번째 줄까지는 체스판 A가, 다섯 번째 줄부터 여덟 번째 줄까지는 체스판 B가 입력으로 주어진다. 0은 비어있는 칸을 의미하고, 1은 나이트가 있는 칸을 의미한다. 체스판 A와 B에 각각 나이트가 적어도 하나 이상 존재하며, 항상 해가 존재함이 보장된다.

출력

나이트들을 옮겨 체스판 A에서 체스판 B로 만드는 데 필요한 나이트들의 최소 이동 횟수를 출력한다.

제한

힌트