软通动力-编程能力在线评测系统

Problem1021--#543. 「LibreOJ β Round #7」奴隶主的游戏

1021: #543. 「LibreOJ β Round #7」奴隶主的游戏

Time Limit: 2 Sec Memory Limit: 1024 MB
Submit: 1 Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

奴隶主家的公告：欢迎和我玩数独游戏，赢了你将获得万贯家财，输了 …… 而你正好看到这则公告

数独游戏的规则是这样的：

初始的时候有一个 $n$ 阶数独（ $n$ 阶数独即边长为 $n^2$ 的分成 $n^2$ 个 $n×nn\times n$ 区域的方格，下图为 $4$ 阶数独），并且已经填了 $k$ 个格子，现在两个人轮流在空格子中填数（当然是你先填啦），每次填完需保证局面合法（合法即要求每个人填完后同行同列同区域不能出现相同数字并且填的数字是 $1,n^2]$ 中的整数），能填必须填，不能填者输。

orzlca

现在你要确定你（先手）是否有必胜策略，以免鲁莽输掉游戏沦为奴隶。

第一行一个整数 $T$ 表示有 $T$ 组数据。

对于每组数据第一行两个整数 $n, k$ 。

接下来有 $k$ 行，每行三个整数 $x, y, z$ 表示第 $x$ 行 $y$ 列填了数字 $z$ 。保证填的格子不重复，且已经填好的数字合法。

对于每组数据输出一个字符串：YES 表示有必胜策略，NO 表示没有必胜策略。

注意：样例中有 $1≤n<41\le n < 4$ 的情况，这只是为了便于解释样例及说明游戏规则，在实际的测试数据中保证 $\ge 4$ 。

样例输入 1

1
1 0

样例输出 1

YES

样例解释 1

初始局面是一个 $1×11\times 1$ 的方块并且没有填，你只要填上 1 就可获胜。

样例输入 2

样例输出 2

NO

样例解释 2

输入即为上图填了 1 和 2 后的局面。

对于所有数据， $4≤n≤15,0≤k≤2,1≤T≤20,1≤x,y,z≤n24\leq n \leq 15,0\leq k \leq 2,1 \leq T \leq 20,1\le x,y,z\le n^2$ 。

保证填的格子不重复，且已经填好的数字合法。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

Subtask #	分值	$n$	$k$
$1$	$17$	$≤6\leq 6$	-
$2$	$25$	$≤11\leq 11$	-
$3$	$12$	-	$= 0$
$4$	$16$	-	$≤1\leq 1$
$5$	$30$	-	-

Source/Category

[Submit] [Status]