2021寒假每日一题《数独检查》.pdf

2021寒假每日一题《数独检查》 数独检查 题目来源：Google Kickstart2013 Round B Problem A 时间限制：\(1000ms\) 内存限制：\(64mb\) 题目描述 数独是一种流行的单人游戏。 目标是用数字填充 \(9*9\) 矩阵，使每列，每行和所有 \(9\) 个非 重叠的 \(3*3\) 子矩阵包含从 \(1\) 到 \(9\) 的所有数字。 每个 \(9*9\) 矩阵在游戏开始时都会有部分数字已经给出，通常有 一个独特的解决方案。 给定完成的 \(N^2 ∗ N^2\) 数独矩阵，你的任务是确定它是否是 有效的解决方案。 有效的解决方案必须满足以下条件： • 每行包含从 \(1\) 到 \(N^2\) 的每个数字，每个数字一次。 • 每列包含从 \(1\) 到 \(N^2\) 的每个数字，每个数字一次。 • 将 \(N^2 ∗ N^2\) 矩阵划分为 \(N^2\) 个非重叠 \(N ∗ N\) 子 矩阵。 每个子矩阵包含从 \(1\) 到 \(N^2\) 的每个数字，每个数字一 次。 你无需担心问题答案的唯一性，只需检查给定矩阵是否是有效的 解决方案即可。 输入格式 第一行包含整数 \(T\) ，表示共有 \(T\) 组测试数据。 每组数据第一行包含整数 \(N\) 。 接下来 \(N^2\) 行，每行包含 \(N^2\) 个数字（均不超过 1000 ）， 用来描述完整的数独矩阵。 输出格式 每组数据输出一个结果，每个结果占一行。 结果表示为“Case #x: y”，其中 x 是组别编号（从 1 开始），如 果给定矩阵是有效方案则 y 是 Yes ，否则y 是 No。 数据范围 \(1 ≤ T ≤ 100\) , \(3 ≤ N ≤ 6\) 样例输入 3 3 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 3 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 3 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 999 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 样例输出 Case #1: Yes Case #2: No Case #3: No 解题思路 数独的规则就是每一行、每一列、每一个、单元都由 \([1,n^2]\) 的数组成，且不能重复。 只需要暴力检查所有的情况就可以得到答案了。 第一步检查： 检查每一行，由于是第一个检查，所以同时检查数 据规模是否在 \([1,n^2]\) 内。 用一个 \(HashSet\) 来存一行中的元素，调用 HashSet.add() 将 这一行的每个数数存入其中，如果数存在，就不会添加进去了。 添加完一行后，调用 Ha