問題
상대편의 말을 뛰어넘어서 잡는 체커게임이 있다. 정올에서는 이 체커 게임을 변형하여 정올리안 체커라는 게임을 만들었다.
정올리안 체커는 가장 적은 말의 이동으로 보드 위에 말을 1개만 남기는 것이 목적이며, 규칙은 다음과 같다.
1. 정사각형 모양의 보드판위에 그려져 있는 정사각형 격자의 한 칸에 하나씩 말을 배치한다.
2. 시작은 보드에 있는 어떤 말이든 가능하며, 상하좌우로 뛰어 넘어 다른 말을 잡는다.
3. 뛰어 넘을 때는 바로 옆 칸에 말이 있을 때이며 2칸 이상은 넘을 수 없다. 이때 잡힌 말은 보드에서 꺼낸다.
4. 넘어온 칸에서 같은 방법으로 이동이 가능하다면 연속으로 말을 잡을 수 있으며, 이 경우는 한 번 이동한 것으로 한다.
위의 예제는 2번이면 가능하다. 맨 처음에 4, 1의 말을 4, 3으로 이동하고, 2, 4의 말을 4, 4로 4, 2로 2, 2로 다시 4, 2로 이동하면 된다.
輸入
입력의 첫줄에는 보드의 크기 N(3≤n≤7)이 들어온다.
그 다음 줄부터 N줄에 걸쳐 N개의 0과 1이 공백으로 구분하여 들어오는데 0은 빈칸 1은 말이다.
輸出
출력의 첫줄에 말의 최소 이동 횟수를 출력한다. 불가능한 경우는 없다.
範例
5
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
1 1 0 0 0
0 0 0 0 0
2
來源
pai2
需要登入才能撰寫程式碼。