당신이 다시 심판이다

시간 제한2초메모리 제한2048 MB

요약

2^n × 2^n 격자에 색 번호가 주어질 때, 빈칸이 정확히 하나이고 L자 트라이오미노로 격자를 모두 덮은 타일링인지 판정한다.

난이도: 보통10점 중 4점
유형: 구현, 시뮬레이션, 배열, 완전 탐색
정답자: 아직 제출이 없습니다

문제

당신은 다시 심판이다! 당신이 심사하는 대회에는 다음 문제가 포함되어 있다.

$\frac{4^n-1}{3}$ 가지 서로 다른 색의 L형 트라이오미노가 각각 하나씩 있다. 이 트라이오미노들로 $2^n \times 2^n$ 격자를 타일링하되, 정확히 한 칸은 비어 있고 나머지 모든 칸은 트라이오미노 한 칸으로 정확히 한 번씩 덮여야 한다. 모든 트라이오미노를 사용해야 한다.

당신의 팀은 이 문제의 채점기를 작성해야 한다. 입력값과 형식 검증은 이미 끝났다. $2^n \times 2^n$ 격자의 타일링이라고 주장하는 것이 주어지며, 격자의 각 칸은 0이거나 $1$ 부터 $\frac{4^n-1}{3}$ 까지의 양의 정수로, 각각 색 하나를 나타낸다. 이것이 정말로 $\frac{4^n-1}{3}$ 개의 서로 다른 트라이오미노와 빈 칸 하나로 격자를 덮은 것인지 판별하라.

L형 트라이오미노는 다음과 같이 생겼다.

입력

첫 줄에 정수 $n$ ( $1 \le n \le 10$ )이 주어진다. 이는 설명에서의 $n$ 이다.

다음 $2^n$ 개 줄 각각에는 $2^n$ 개의 정수 $x$ ( $0 \le x \le \frac{4^n-1}{3}$ )가 주어진다. 0은 빈 칸을 나타내고, 양의 정수는 트라이오미노의 고유한 식별자이다.

출력

주어진 격자가 $\frac{4^n-1}{3}$ 개의 서로 다른 트라이오미노와 빈 칸 하나로 덮여 있으면 $1$ , 그렇지 않으면 $0$ 을 출력한다.

예제2

예제 1
입력
```
2
1 1 2 2
1 3 3 2
4 4 3 5
4 0 5 5
```
예상 출력
```
1
```
예제 2
입력
```
1
1 1
1 1
```
예상 출력
```
0
```