You be The Judge, Again

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

요약

2^n 곱하기 2^n 격자가 주어질 때, 빈칸이 정확히 하나이고 나머지 칸을 서로 다른 L-트라이오미노가 모두 덮는지 판정한다.

난이도: 보통10점 중 4점
유형: 구현, 행렬, 해시맵, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

You are a judge, again! The contest you're judging includes the following problem:

You have one L-shaped triomino of each of $\frac{4^n-1}{3}$ different colors. Tile a $2^n$ by $2^n$ grid using each of these triominos such that there is exactly one blank square and all other squares are covered by exactly one square of such a triomino. All triominos must be used."

Your team is to write a checker for this problem. Validation of the input values and format has already taken place. You will be given a purported tiling of a $2^n$ by $2^n$ grid, where each square in the grid is either 0 or a positive integer from $1$ to $\frac{4^n-1}{3}$ representing one of the colors. Determine if it is, indeed, a covering of the grid with $\frac{4^n-1}{3}$ unique triominos and a single empty space.

L-shaped triominos look like this:

입력

The first line of input contains a single integer $n$ ( $1 \le n \le 10$ ), which is the $n$ of the description.

Each of the next $2^n$ lines contains $2^n$ integers $x$ ( $0 \le x \le \frac{4^n-1}{3}$ ), where 0 represents an empty space, and any positive number is a unique identifier of a triomino.

출력

Output a single integer, which is $1$ if the given grid is covered with $\frac{4^n-1}{3}$ unique triominos and a single empty space. Otherwise, output $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
```