📝 题目大意

给定一个 $9 \times 9$ 的方格，每个格子填有 $1$ 到 $9$ 的整数。判断是否构成一个合法的数独（Sudoku），即每行、每列、每个 $3 \times 3$ 宫格内都恰好包含 $1$ 到 $9$ 各一次。

💡 解题思路

1. 题目分析：方格大小固定为 $9 \times 9$，每个格子数值范围为 $[1, 9]$。需要同时验证三个条件——行、列和 $3 \times 3$ 宫格的无重复性。由于输入规模极小（$81$ 个格子），直接模拟检查即可，无需任何优化。

2. 算法推导：

   • 使用 bool ok = true 作为全局合法性标志，一旦某处发现重复立即置为 false 并提前退出。
   • 行检查：遍历每一行 i（0 到 8），用长度为 $10$ 的布尔数组 seen 标记该行已出现的数字。若 seen[val] 已为 true，说明该行出现了重复数字，ok = false 并跳出。
   • 列检查：仅当行检查通过（ok == true）时继续。遍历每一列 j，同样用 seen 数组检查该列有无重复。
   • 宫格检查：仅当前两步均通过时继续。将 $9$ 个 $3 \times 3$ 宫格编号为 block = 0..8，通过 startRow = (block / 3) * 3 和 startCol = (block % 3) * 3 计算每个宫格的左上角坐标，然后遍历宫格内的 $3 \times 3$ 个格子，同样用 seen 数组去重。
   • 最终根据 ok 输出 "Yes" 或 "No"。

3. 边界与细节：

   • 题目保证 $1 \leq A_{i,j} \leq 9$，因此 seen 数组大小设为 $10$（下标 $1$ 到 $9$ 有效）不会越界。
   • 每个检查阶段都要在发现重复后立即 break，避免后续无意义的遍历（同时也防止 seen 数组被重新初始化后覆盖了错误状态）。
   • 宫格检查中 block / 3 和 block % 3 分别对应行号和列号，乘以 $3$ 得到起始坐标，这是数独宫格遍历的常见技巧。

⏱️ 复杂度分析

• 时间复杂度：$O(9 \times 9) = O(1)$，每个格子被检查常数次（行、列、宫格各一次）。
• 空间复杂度：$O(1)$，仅需一个长度为 $10$ 的布尔数组及 $9 \times 9$ 的输入矩阵。

💻 标准代码 (C++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读入 9x9 方格
    vector<vector<int>> A(9, vector<int>(9));
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> A[i][j];
        }
    }

    bool ok = true;  // 全局合法性标志

    // 1. 检查每一行是否有重复数字
    for (int i = 0; i < 9; i++) {
        vector<bool> seen(10, false);  // seen[x] 表示数字 x 是否在该行出现过
        for (int j = 0; j < 9; j++) {
            int val = A[i][j];
            if (seen[val]) {  // 重复出现，不合法
                ok = false;
                break;
            }
            seen[val] = true;
        }
        if (!ok) break;  // 提前退出
    }

    // 2. 检查每一列是否有重复数字（仅当行检查通过时进行）
    if (ok) {
        for (int j = 0; j < 9; j++) {
            vector<bool> seen(10, false);  // seen[x] 表示数字 x 是否在该列出现过
            for (int i = 0; i < 9; i++) {
                int val = A[i][j];
                if (seen[val]) {  // 重复出现，不合法
                    ok = false;
                    break;
                }
                seen[val] = true;
            }
            if (!ok) break;  // 提前退出
        }
    }

    // 3. 检查每个 3x3 宫格是否有重复数字（仅当前两步均通过时进行）
    if (ok) {
        for (int block = 0; block < 9; block++) {
            // 计算当前宫格的左上角坐标
            int startRow = (block / 3) * 3;
            int startCol = (block % 3) * 3;
            vector<bool> seen(10, false);  // seen[x] 表示数字 x 是否在该宫格出现过
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    int val = A[startRow + i][startCol + j];
                    if (seen[val]) {  // 重复出现，不合法
                        ok = false;
                        break;
                    }
                    seen[val] = true;
                }
                if (!ok) break;  // 提前退出内层循环
            }
            if (!ok) break;  // 提前退出外层循环
        }
    }

    // 输出结果
    cout << (ok ? "Yes" : "No") << endl;
    return 0;
}