석판 자르기
시간 제한2초메모리 제한128 MB
N x N 돌판을 가로/세로 방향이 번갈아 바뀌는 직선 절단으로 반복해서 잘라, 모든 조각이 불순물 없이 정확히 하나의 결정을 포함하게 만드는 방법의 수를 구합니다.
문제
석판은 빈 칸, 불순물, 보석 결정체가 있는 N x N 격자로 주어진다. 석판을 여러 조각으로 나누어, 최종적으로 모든 조각이 다음 조건을 만족하게 하려고 한다.
- 조각 안에는 불순물이 없어야 한다.
- 조각 안에는 보석 결정체가 정확히 하나 있어야 한다.
불순물을 제거하려면 그 불순물이 있는 칸을 지나는 직선으로 잘라야 한다. 석판의 결 때문에 한 번의 절단은 가로 또는 세로 방향으로만 할 수 있다. 처음 절단은 어느 방향이든 가능하지만, 어떤 조각을 다시 자를 때는 바로 직전에 그 조각을 만든 절단과 같은 방향으로 자를 수 없다.
절단선은 현재 조각을 완전히 가로질러 두 개의 조각으로 나누어야 한다. 절단선 위에 보석 결정체가 있으면 자를 수 없다. 가능한 절단 과정을 모두 세어 출력하라.
입력
첫째 줄에 석판의 크기 N이 주어진다. 1 <= N <= 20이다.
다음 N줄에는 석판의 상태가 주어진다. 각 줄에는 N개의 정수가 공백으로 구분되어 주어진다.
0: 빈 칸1: 불순물2: 보석 결정체
보석 결정체의 수는 15개를 넘지 않는다.
출력
각 최종 조각에 불순물이 없고 보석 결정체가 정확히 하나씩 들어가도록 석판을 나누는 방법의 수를 출력한다.
가능한 방법이 없으면 -1을 출력한다.