7-15 九宫格分数 20 全屏浏览 切换布局 作者 陈越 单位 浙江大学 九宫格是一款数字游戏，传说起源于河图洛书，现代数学中称之为三阶幻方。游戏规则是：将一个 9×9 的正方形区域划分为 9 个 3×3 的正方形宫位，要求 1 到 9 这九个数字中的每个数字在每一行、每一列、每个宫位中都只能出现一次。 本题并不要求你写程序解决这个问题，只是对每个填好数字的九宫格，判断其是否满足游戏规则的要求。 输入格式： 输入首先在第一行给出一个正整数 n（≤10），随后给出 n 个填好数字的九宫格。每个九宫格分 9 行给出，每行给出 9 个数字，其间以空格分隔。 输出格式： 对每个给定的九宫格，判断其中的数字是否满足游戏规则的要求。满足则在一行中输出 1，否则输出 0。 输入样例： 3 5 1 9 2 8 3 4 6 7 7 2 8 9 6 4 3 5 1 3 4 6 5 7 1 9 2 8 8 9 2 1 4 5 7 3 6 4 7 3 6 2 8 1 9 5 6 5 1 7 3 9 2 8 4 9 3 4 8 1 6 5 7 2 1 6 7 3 5 2 8 4 9 2 8 5 4 9 7 6 1 3 8 2 5 4 9 7 1 3 6 7 9 6 5 1 3 8 2 4 3 4 1 6 8 2 7 9 5 6 8 4 2 7 1 3 5 9 9 1 2 8 3 5 6 4 7 5 3 7 9 6 4 2 1 8 2 7 9 1 5 8 4 6 3 4 5 8 3 2 6 9 7 1 1 6 3 7 4 9 5 8 3 81 2 5 4 9 7 1 3 6 7 9 6 5 1 3 8 2 4 3 4 1 6 8 2 7 9 5 6 8 4 2 7 1 3 5 9 9 1 2 8 3 5 6 4 7 5 3 7 9 6 4 2 1 8 2 7 9 1 5 8 4 6 3 4 5 8 3 2 6 9 7 1 1 6 3 7 4 9 5 8 2 输出样例： 1 0 0 编写代码使用c++

<think>好的，我现在需要解决这个九宫格的问题。题目要求判断给定的九宫格是否符合数独规则，即每一行、每一列、每个3x3的宫位都包含1到9的数字且不重复。输入是多个填好的九宫格，每个需要输出1或0表示是否合法。 首先，我得想清楚如何检查这三个条件。对于每个九宫格，我需要分别检查行、列和宫位。那具体怎么实现呢？ 检查行的话，每行遍历一遍，看是否有重复的数字。列的话类似，但需要遍历每一列的所有行。宫位可能比较复杂，因为需要确定每个宫的起始位置，然后检查该3x3区域内的数字是否重复。 那如何分割宫位呢？比如，整个九宫格分成9个3x3的宫。第一个宫的行是0-2，列0-2，第二个宫的行0-2，列3-5，第三个行0-2列6-8。然后中间的是行3-5，列0-2等等。所以每个宫的起始行是row_start = (宫号 / 3) * 3，起始列col_start = (宫号 % 3) *3？或者可能宫号的遍历方式需要调整。比如，宫位的索引可以按行优先排列，比如第一个宫是0行0列，第二个是0行3列，第三个0行6列，第四个3行0列，依此类推。所以每个宫对应的起始行是i的0、3、6，对应的起始列是j的0、3、6。例如，宫位的索引可以遍历0到8，然后计算起始行和列。 或者，对于每个宫位，可以用三重循环：对于每个大行（每三个行），每个大列（每三个列），然后检查这个大行和大列对应的3x3宫。 比如，外层循环处理每个宫的起始行是0,3,6，内层处理起始列0,3,6。这样总共有3*3=9宫。每个宫内的每个格子遍历起始行到起始行+2，起始列到起始列+2。 接下来，具体的检查步骤： 对于每个九宫格： 1. 检查每一行是否有重复，并且数字是否全在1-9之间。 2. 检查每一列是否有重复。 3. 检查每个宫位是否有重复。 只要有一个条件不满足，整个九宫格就不合法，返回0。 那么，如何处理这些检查呢？ 对于行检查，可以遍历每一行，用一个哈希集合或者数组来记录出现过的数字。如果有重复或者数字不在1-9范围内，就返回0。 列检查类似，不过要遍历每一列，即对于每列c，遍历所有行r，检查grid[r][c]。 宫位检查的话，遍历每个宫的起始行和列，然后检查该3x3区域内的所有数字。 那如何高效实现这三个检查？ 可能的步骤： 对于每个九宫格： - 首先检查行：每一行中的每个数字是否唯一且在1-9之间。 - 然后检查列：每一列中的每个数字是否唯一。 - 最后检查宫位：每个宫中的数字是否唯一。 这三个条件必须全部满足才合法。 接下来，如何处理输入？每个测试用例是9行，每行9个数字。需要读取n个这样的九宫格。 注意输入的每个数字必须是1-9之间的整数，否则直接不合法。比如，题目中的第三个输入样例中的第一行有一个81，这显然超过了9，所以该宫格直接返回0。 所以在检查时，首先要确保每个元素的值在1到9之间。否则直接标记为非法。 那步骤可能调整为： 对于每个九宫格： - 首先检查每个元素是否是1-9之间的数。如果有任何一个不是，直接返回0。 - 否则，检查所有行、列、宫位是否有重复。 那这三个条件必须同时满足。 那具体如何实现？比如，在C++中，可以用一个二维数组来存储每个九宫格的数据。例如，int grid[9][9]。 然后，对于行检查，可以循环每一行，每一行里，用set或者数组来记录出现过的数字。例如，对于每行，创建一个大小为10的布尔数组，初始为false。遍历该行的每个元素，如果元素的值不在1-9之间，返回false。否则，如果对应的布尔数组的位置已经是true，说明重复，返回false。否则，标记为true。 同样的逻辑适用于列和宫位。 那这三个检查可以分开写函数，或者用循环处理。 现在，如何高效地实现这些检查？ 比如，行检查： for (int i=0; i<9; i++) { bool exists[10] = {false}; for (int j=0; j<9; j++) { int num = grid[i][j]; if (num <1 || num>9) return false; if (exists[num]) return false; exists[num] = true; } } 同理，列检查： for (int j=0; j<9; j++) { bool exists[10] = {false}; for (int i=0; i<9; i++) { int num = grid[i][j]; if (exists[num]) return false; exists[num] = true; } } 宫位检查： for (int blockRow=0; blockRow<3; blockRow++) { for (int blockCol=0; blockCol<3; blockCol++) { bool exists[10] = {false}; for (int i=0; i<3; i++) { for (int j=0; j<3; j++) { int actualRow = blockRow *3 + i; int actualCol = blockCol *3 + j; int num = grid[actualRow][actualCol]; if (exists[num]) return false; exists[num] = true; } } } } 或者另一种方式是，每个宫的起始行是i*3，起始列是j*3，其中i和j在0-2之间。 或者，将宫位按照顺序0-8来处理，每个宫的起始行和列可以计算为： 宫号从0到8： startRow = (block /3) *3; startCol = (block %3) *3; 比如，block=0时，startRow=0，startCol=0；block=1，startRow=0，startCol=3；block=3，startRow=3，startCol=0等。 这样，循环block从0到8，每个块检查对应的3x3区域。 这样处理的话： for (int block =0; block <9; block++) { int startRow = (block /3)*3; int startCol = (block %3)*3; bool exists[10] = {false}; for (int i=0; i<3; i++) { for (int j=0; j<3; j++) { int row = startRow +i; int col = startCol +j; int num = grid[row][col]; if (exists[num]) return false; exists[num] = true; } } } 这可能更容易编写循环。 综上，总体的步骤是： 对每个九宫格： 1. 检查所有元素是否在1-9之间。如果存在不在范围内的数，直接返回0。 2. 检查所有行是否有重复。 3. 检查所有列是否有重复。 4. 检查所有宫位是否有重复。 如果以上都满足，返回1，否则返回0。 接下来，如何处理输入？ 每个测试用例是9行，每行9个数字。需要读取n次这样的九宫格。 在C++中，可以用二维数组来保存每个九宫格的数据。例如： int n; cin >>n; for (int k=0; k<n; k++) { int grid[9][9]; for (int i=0; i<9; i++) { for (int j=0; j<9; j++) { cin >> grid[i][j]; } } // 检查并输出结果 } 接下来，如何编写检查函数？ 可以写一个函数，参数是grid，返回是否满足条件。 函数的大致结构： bool isValid(int grid[9][9]) { // 检查每个元素是否为1-9 for (int i=0; i<9; i++) { for (int j=0; j<9; j++) { if (grid[i][j] <1 || grid[i][j]>9) { return false; } } } // 检查行 for (int i=0; i<9; i++) { bool exists[10] = {false}; for (int j=0; j<9; j++) { int num = grid[i][j]; if (exists[num]) return false; exists[num] = true; } } // 检查列 for (int j=0; j<9; j++) { bool exists[10] = {false}; for (int i=0; i<9; i++) { int num = grid[i][j]; if (exists[num]) return false; exists[num] = true; } } // 检查宫位 for (int block=0; block<9; block++) { int startRow = (block /3)*3; int startCol = (block %3)*3; bool exists[10] = {false}; for (int i=0; i<3; i++) { for (int j=0; j<3; j++) { int row = startRow +i; int col = startCol +j; int num = grid[row][col]; if (exists[num]) return false; exists[num] = true; } } } return true; } 这样，在函数中，先检查所有元素是否有效，然后检查行、列、宫位。 但是，这样可能会存在重复检查的问题。例如，在检查行的时候，每个元素已经被检查过是否在1-9之间，所以后面的列和宫位检查可能不需要再检查。所以在实际中，可以将元素的有效性检查单独放在最前面，这样后面的检查可以假设所有数字都是有效的，从而避免重复判断。 但是根据题目中的输入样例，第三个测试用例中的某个数字是81，显然不在1-9范围内，所以这时候需要返回0。 现在，需要注意，当在元素有效性检查中发现任何一个数字不在1-9范围内，整个九宫格无效，直接返回false。此时后续的检查都不需要执行了。 所以，函数的结构是正确的。 现在，编写代码的时候，需要注意二维数组的传递方式。例如，在C++中，可以将函数参数写成int grid[9][9]，或者使用指针等方式。 但是，在函数参数传递中，二维数组的大小需要明确。所以在代码中，可以这样处理： 在main函数中读取每个九宫格到int grid[9][9]中，然后调用isValid(grid)。 然后，根据函数的返回结果，输出1或0。 现在，测试样例中的第三个输入案例： 第三组输入中的某行是否有问题？比如，第三组的输入样例的第三个九宫格最后一行是“1 6 3 7 4 9 5 8 2”，这看起来没问题。但原题给出的输出是第三个输出是0。可能我之前看错了？ 原题的输出样例是： 输入样例： 3 第一个九宫格是正确的，输出1。第二个九宫格的最后一个行是“1 6 3 7 4 9 5 8 3”，也就是最后一个数字是3，导致该行有两个3，所以行检查不通过。所以第二个输出是0。第三个九宫格可能是否正确？ 第三个九宫格的输入是否合法？原题中的第三个九宫格的输入可能是否有问题？例如，原输入样例中的第三个九宫格： 第三组数据的第一行是“81 2 5 4 9 7 1 3 6”，其中第一个数字是81，显然超过9，所以该九宫格直接返回0。所以第三个输出是0。这样样例的输出是1、0、0，与题目给出的输出样例一致。 因此，在代码中，元素的有效性检查是必须的，可以正确处理这种情况。 现在，代码的编写需要注意输入是否正确读取。例如，在输入时，每个九宫格的9行，每行有9个数字，用空格分隔。 在C++中，可以用循环读取每个数字。例如： for (int i=0; i<9; i++) { for (int j=0; j<9; j++) { cin >> grid[i][j]; } } 这样是正确的吗？假设输入中的每个数字都是正确的，不会有其他字符干扰。 题目中的输入样例第三组的第一个数字是81，这会被正确读取为一个整数，此时会被检测到不在1-9范围内，从而整个九宫格返回0。 所以，代码中的元素有效性检查是正确的。 现在，剩下的问题就是如何将所有这些逻辑用C++代码实现。 现在，编写代码的大致结构： #include <iostream> using namespace std; bool isValid(int grid[9][9]) { // 检查每个元素是否在1-9之间 for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (grid[i][j] < 1 || grid[i][j] > 9) { return false; } } } // 检查行 for (int i = 0; i < 9; ++i) { bool exists[10] = {false}; for (int j = 0; j < 9; ++j) { int num = grid[i][j]; if (exists[num]) { return false; } exists[num] = true; } } // 检查列 for (int j = 0; j < 9; ++j) { bool exists[10] = {false}; for (int i = 0; i < 9; ++i) { int num = grid[i][j]; if (exists[num]) { return false; } exists[num] = true; } } // 检查宫位 for (int block = 0; block < 9; ++block) { int startRow = (block / 3) * 3; int startCol = (block % 3) * 3; bool exists[10] = {false}; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { int row = startRow + i; int col = startCol + j; int num = grid[row][col]; if (exists[num]) { return false; } exists[num] = true; } } } return true; } int main() { int n; cin >> n; while (n--) { int grid[9][9]; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { cin >> grid[i][j]; } } cout << (isValid(grid) ? "1" : "0") << endl; } return 0; } 这样应该可以解决问题。 现在，测试样例中的第二个九宫格： 例如，第三个宫格的最后一行是“1 6 3 7 4 9 5 8 3”——最后一个数是3，导致该行有两个3，所以行检查不通过，返回0。 第三个宫格的第一行是81，元素有效性检查失败，返回0。 所以，样例的输出是1、0、0，与题目要求一致。 现在，代码是否正确？ 可能存在的疑问：宫位检查中的block处理是否正确？ 比如，block从0到8，每个block对应的startRow和startCol是否正确？ 例如： block=0 → startRow=0, startCol=0 → 宫位0-2行，0-2列。 block=1 → startRow=0, startCol=3 → 宫位0-2行，3-5列。 block=2 → startRow=0, startCol=6 → 0-2行，6-8列。 block=3 → startRow=3, startCol=0 →3-5行，0-2列。 block=4 →3-5行，3-5列。 依此类推。这符合宫位的划分。 所以，宫位的检查是正确的。 综上，这样的代码应该能正确解决问题。</think>```cpp #include <iostream> using namespace std; bool isValid(int grid[9][9]) { // 检查每个数字是否在1-9范围内 for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (grid[i][j] < 1 || grid[i][j] > 9) { return false; } } } // 检查每行是否有重复 for (int i = 0; i < 9; ++i) { bool exists[10] = {false}; for (int j = 0; j < 9; ++j) { int num = grid[i][j]; if (exists[num]) return false; exists[num] = true; } } // 检查每列是否有重复 for (int j = 0; j < 9; ++j) { bool exists[10] = {false}; for (int i = 0; i < 9; ++i) { int num = grid[i][j]; if (exists[num]) return false; exists[num] = true; } } // 检查每个3x3宫位 for (int block = 0; block < 9; ++block) { int startRow = (block / 3) * 3; int startCol = (block % 3) * 3; bool exists[10] = {false}; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { int num = grid[startRow + i][startCol + j]; if (exists[num]) return false; exists[num] = true; } } } return true; } int main() { int n; cin >> n; while (n--) { int grid[9][9]; for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) cin >> grid[i][j]; cout << (isValid(grid) ? "1" : "0") << endl; } return 0; } ``` ### 代码解释 1. **输入处理**：首先读取测试用例数 `n`，然后逐个读取每个九宫格的数据到二维数组 `grid` 中。 2. **有效性检查**： - **数值范围**：检查所有元素是否在1-9之间。 - **行检查**：每行使用布尔数组标记已出现的数字，确保无重复。 - **列检查**：每列同样使用布尔数组标记，确保无重复。 - **宫位检查**：将九宫格划分为9个3x3的小宫格，逐个检查每个小宫格内的数字是否重复。 3. **输出结果**：根据检查结果输出1（合法）或0（非法）。 该算法时间复杂度为 $O(n \times 9^2)$，能高效处理题目中的输入规模。