석판 자르기

석판은 빈 칸, 불순물, 보석 결정체가 있는 N x N 격자로 주어진다. 석판을 여러 조각으로 나누어, 최종적으로 모든 조각이 다음 조건을 만족하게 하려고 한다.

• 조각 안에는 불순물이 없어야 한다.
• 조각 안에는 보석 결정체가 정확히 하나 있어야 한다.

불순물을 제거하려면 그 불순물이 있는 칸을 지나는 직선으로 잘라야 한다. 석판의 결 때문에 한 번의 절단은 가로 또는 세로 방향으로만 할 수 있다. 처음 절단은 어느 방향이든 가능하지만, 어떤 조각을 다시 자를 때는 바로 직전에 그 조각을 만든 절단과 같은 방향으로 자를 수 없다.

절단선은 현재 조각을 완전히 가로질러 두 개의 조각으로 나누어야 한다. 절단선 위에 보석 결정체가 있으면 자를 수 없다. 가능한 절단 과정을 모두 세어 출력하라.

첫째 줄에 석판의 크기 N이 주어진다. 1 <= N <= 20이다.

다음 N줄에는 석판의 상태가 주어진다. 각 줄에는 N개의 정수가 공백으로 구분되어 주어진다.

• 0: 빈 칸
• 1: 불순물
• 2: 보석 결정체

보석 결정체의 수는 15개를 넘지 않는다.

각 최종 조각에 불순물이 없고 보석 결정체가 정확히 하나씩 들어가도록 석판을 나누는 방법의 수를 출력한다.

가능한 방법이 없으면 -1을 출력한다.