题目描述

你又双叒叕当上裁判了！你正在评判的比赛包含下面这道题：

“你有 $\frac{4^n - 1}{3}$ 种不同颜色的 L 形三格骨牌，每种颜色恰好有一张。请用所有这些三格骨牌覆盖一个 $2^n \times 2^n$ 的网格，使得恰好有一个格子是空的，其余所有格子都被恰好一个三格骨牌的一个方格覆盖。所有三格骨牌都必须被使用。”

你的团队需要为这道题编写一个检验器（checker）。输入数值和格式的合法性校验已经完成。你会得到一个声称的 $2^n \times 2^n$ 网格的覆盖方案，其中每个格子要么是 $0$，要么是 $1$ 到 $\frac{4^n - 1}{3}$ 之间的一个正整数，表示该格子所属的骨牌颜色。请判断它是否确实是由 $\frac{4^n - 1}{3}$ 个互不相同的三格骨牌以及一个空格子所构成的有效覆盖。

L 形三格骨牌的形状如下：

:::align{center} :::

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 10$），含义如上所述。

接下来的 $2^n$ 行，每行包含 $2^n$ 个整数 $x$（$0 \le x \le \frac{4^n - 1}{3}$），其中 $0$ 表示空格子，任何正数表示该格子所属的三格骨牌的唯一标识符。

输出格式

输出一个整数，如果给定的网格确实是由 $\frac{4^n - 1}{3}$ 个互不相同的三格骨牌以及一个空格子所构成的有效覆盖，则输出 $1$；否则输出 $0$。

2
1 1 2 2
1 3 3 2
4 4 3 5
4 0 5 5

1

1
1 1
1 1

0

提示

翻译由 DeepSeek V3.2 完成