기사들의 여행

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

잘못 산 체스판을 어떻게 처리할지 고민하던 창현이와 예환이는 나이트가 배치된 체스판 A, B를 각각 그렸다. 그리고 A의 나이트 위치를 B와 같게 만드는 데 필요한 최소 이동 횟수를 늦게 구하는 사람이 치우기로 하였다. 창현이는 치우는 게 귀찮아서 꼭 이기고 싶다.

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

첫 번째 줄부터 네 번째 줄까지는 체스판 A가, 다섯 번째 줄부터 여덟 번째 줄까지는 체스판 B가 주어진다. 0은 빈 칸을, 1은 나이트가 있는 칸을 뜻한다. 체스판 A와 B에는 각각 나이트가 적어도 하나 이상 있으며, 항상 해가 존재함이 보장된다.

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