전자 기판

정사각형 기판의 윗면에 정사각격자 모양의 격자가 새겨져 있다. 두 격자선이 만나는 지점을 마디(node)라고 부르며, 기판에는 n행 n열로 배열된 n × n 개의 마디가 있다. 가장 바깥쪽 행 또는 열에 놓인 마디를 경계 마디라고 한다.

일부 마디에는 핀(pin)이 놓여 있다. 우리는 격자를 따라 놓이는 전자 회로로 핀을 기판의 경계에 연결하려 하며, 다음 규칙을 따른다.

• 회로는 격자선을 따라서만 놓이며, 서로 인접한(상하좌우로 붙은) 마디 사이를 이동한다. 대각선 방향으로는 놓을 수 없다.
• 어느 두 회로도 공통된 점을 가질 수 없다. 따라서 두 회로가 같은 격자선 구간을 공유하거나 같은 마디를 지나갈 수 없다. 즉, 모든 회로는 마디를 공유하지 않는다.
• 회로는 경계를 따라 놓일 수 없다. 처음으로 경계 마디에 도달하는 순간 반드시 끝난다.
• 회로는 다른 핀이 놓인 마디를 지나거나 그 위에서 끝낼 수 없다.

이미 경계 마디 위에 놓인 핀은 이미 연결된 것으로 보며, 별도의 회로가 필요 없다.

그림. 핀이 놓인 기판(가운데)과 유효한 회로 연결의 예(오른쪽).

회로로 경계에 연결할 수 있는 핀의 최대 개수를 구하라(즉, 마디를 공유하지 않게 놓을 수 있는 회로의 최대 개수). 이미 경계 위에 있는 핀은 회로가 필요 없으므로 세지 않는다.

첫 줄에는 정수 n (3 ≤ n ≤ 15)이 주어진다.

이어지는 n개의 줄에는 각각 공백 하나로 구분된 n개의 숫자가 주어진다. 각 숫자는 1 또는 0이며, 1은 핀이 놓인 마디를, 0은 비어 있는 마디를 뜻한다. 줄은 맨 위 행부터 맨 아래 행까지, 각 줄 안에서는 가장 왼쪽 열부터 가장 오른쪽 열까지의 순서로 주어진다.

위 규칙을 모두 지키는, 마디를 공유하지 않는 회로로 경계에 연결할 수 있는 핀의 최대 개수를 정수 하나로 출력한다.