A16870. Bingo Candies
编程题
入门
知识点
题目描述
Alice 有一块魔法棋盘。棋盘是一个 $n\times n$ 的网格，每个格子里有一颗有颜色的糖果。第 $i$ 行第 $j$ 列的糖果颜色用 $a_{i,j}$ 表示。
Bob 想知道，是否存在一种重排棋盘的方法，使得没有任何一行或一列由 $n$ 颗同色的糖果组成。
你的任务是判断是否存在这样的重排。
Bob 想知道，是否存在一种重排棋盘的方法，使得没有任何一行或一列由 $n$ 颗同色的糖果组成。
你的任务是判断是否存在这样的重排。
输入格式
每组测试数据包含多组测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 500$）。每组测试用例描述如下：
每组测试用例的第一行为一个整数 $n$（$1 \le n \le 100$），表示棋盘的大小。
接下来的 $n$ 行，每行包含 $n$ 个整数，第 $i$ 行第 $j$ 个整数为 $a_{i,j}$（$1 \le a_{i,j} \le n^2$），表示棋盘上糖果的颜色。
保证所有测试用例中 $n$ 的和不超过 $500$。
每组测试用例的第一行为一个整数 $n$（$1 \le n \le 100$），表示棋盘的大小。
接下来的 $n$ 行，每行包含 $n$ 个整数，第 $i$ 行第 $j$ 个整数为 $a_{i,j}$（$1 \le a_{i,j} \le n^2$），表示棋盘上糖果的颜色。
保证所有测试用例中 $n$ 的和不超过 $500$。
输出格式
对于每组测试用例，若存在满足条件的棋盘重排，输出 "YES"；否则输出 "NO"。
输出时大小写不敏感。例如，"yEs"、"yes"、"Yes" 和 "YES" 都被认为是肯定的回答。
输出时大小写不敏感。例如，"yEs"、"yes"、"Yes" 和 "YES" 都被认为是肯定的回答。
输入输出样例
输入 #1
3 3 1 2 3 3 1 4 4 1 2 3 1 1 1 2 3 4 1 4 3 3 1 1 1 1 1 1 1 1 2
输出 #1
YES YES NO
说明/提示
在第一组测试用例中，没有任何一行或一列的糖果颜色全部相同，因此可直接保留原棋盘即可。
在第二组测试用例中，第一行全部为颜色 $1$。通过交换 $a_{1,1}$ 与 $a_{2,1}$，可以重排棋盘。重排后棋盘如下：
$$ \begin{matrix} 2 & 1 & 1 \\ 1 & 3 & 4 \\ 1 & 4 & 3 \end{matrix} $$
现在没有任何一行或一列全部由同色糖果组成。
在第三组测试用例中，无论如何重排，始终会有一行或一列全部由颜色 $1$ 构成。因此不存在满足条件的重排。
在第二组测试用例中，第一行全部为颜色 $1$。通过交换 $a_{1,1}$ 与 $a_{2,1}$，可以重排棋盘。重排后棋盘如下：
$$ \begin{matrix} 2 & 1 & 1 \\ 1 & 3 & 4 \\ 1 & 4 & 3 \end{matrix} $$
现在没有任何一行或一列全部由同色糖果组成。
在第三组测试用例中，无论如何重排，始终会有一行或一列全部由颜色 $1$ 构成。因此不存在满足条件的重排。