第十六届蓝桥杯省赛 C/C++ 大学 A 组真题解析

运行结果

在本地运行上述代码，最终输出的数字即为第 2025 个质数。该数为：17627。

题目二：黑白棋

题目回顾与核心规则

在一个 6x6 的棋盘上，已有部分格子填有黑色 (1) 或白色 (0) 棋子，需要填满所有空格，并满足以下规则：

1. 数量相等：每一行和每一列中，黑棋和白棋的数量必须相等（即各有 3 个）。
2. 无三连：在任何一行或一列中，不能有超过两个相同颜色的棋子连续排列（即禁止出现'111'或'000'）。
3. 行列唯一：每一行的排列方式必须是唯一的（不能与其他任何行相同）；每一列的排列方式也必须是唯一的（不能与其他任何列相同）。但行与列之间可以相同。

核心解题思路：深度优先搜索（DFS）+ 剪枝

程序的核心思想是深度优先搜索（DFS），逐个格子地去尝试填入黑棋 (1) 或白棋 (0)。必须在搜索过程中进行严格的剪枝，提前排除那些不可能满足规则的分支。 主要剪枝策略：

1. 数量限制：在放置一个棋子前，检查其所在行和列中，该颜色棋子数量是否已达到 3 个。如果已达到，就不能再放。
2. 无三连限制：在放置一个棋子后，立即检查它是否与其左边两个（或上边两个）棋子构成了连续三个相同颜色。如果构成了，这个分支就是无效的，必须回退。
3. 行列唯一性剪枝：每当填完一整行或一整列时，立即检查该行（或列）的排列是否与之前已完成的任何一行（或列）重复。如果重复，则剪枝。

C++ 完整源码

#include <bits/stdc++.h>
using namespace std;

// 初始化棋盘，-1 表示空格
int grid[6][6] = {
    { 1, 0, 1, 0,-1,-1},
    {-1,-1,-1, 0,-1,-1},
    {-1,-1,-1, 1, 0, 0},
    {-1,-1,-1,-1,-1,-1},
    {-1,-1, 1,-1,-1, 1},
    {-1, 0,-1,-1, 1,-1}
};

// 用于记录当前每行和每列中黑棋 (1) 和白棋 (0) 的数量
int black_row[6] = {0}, black_col[6] = {0};
int white_row[6] = {0}, white_col[6] = {0};

// 用于记录已经出现过的行排列和列排列，以实现'行列唯一性'的剪枝
unordered_set<string> vis_row, vis_col;
string ans; // 存储最终的答案字符串

// 函数：在搜索结束时，对整个棋盘进行一次最终检查
int check() {
    unordered_set<string> r, c;
    // 检查所有行是否唯一
    for (int i = 0; i < 6; i++) {
        string rr = "";
        for (int j = 0; j < 6; j++) rr += to_string(grid[i][j]);
        if (r.count(rr)) return 0; // 发现重复行，无效
        r.insert(rr);
    }
    // 检查所有列是否唯一
    for (int i = 0; i < 6; i++) {
        string cc = "";
        for (int j = 0; j < 6; j++) cc += to_string(grid[j][i]);
        if (c.count(cc)) return 0; // 发现重复列，无效
        c.insert(cc);
    }
    return 1; // 所有检查通过
}

// 核心：深度优先搜索函数，pos 表示当前正在处理的格子编号（从 0 到 35）
int solve(int pos) {
    // 如果所有格子都处理完了，进行最终检查
    if (pos == 36) {
        if (check()) {
            ans = "";
            for (int i = 0; i < 6; i++)
                for (int j = 0; j < 6; j++) ans += to_string(grid[i][j]);
            return 1; // 找到答案，返回 1
        }
        return 0;
    }

    int row = pos / 6; // 计算当前格子所在行
    int col = pos % 6; // 计算当前格子所在列

    // 如果当前格子已经有棋子（非空格），则直接跳过，处理下一个格子
    if (grid[row][col] != -1) return solve(pos + 1);

    // 尝试在当前空格放入两种颜色的棋子：val = 0 (白棋) 或 1 (黑棋)
    for (int val = 0; val <= 1; val++) {
        // 剪枝 1：检查行和列中该颜色的数量是否已达上限（3 个）
        if (!val) { // 尝试放白棋
            if (white_row[row] >= 3 || white_col[col] >= 3) continue;
        } else { // 尝试放黑棋
            if (black_row[row] >= 3 || black_col[col] >= 3) continue;
        }

        // 剪枝 2：检查是否会形成横向或纵向的三个连续相同棋子
        // 横向检查：当前格子的左边两个是否和当前尝试的 val 相同
        if (col >= 2 && grid[row][col - 2] == val && grid[row][col - 1] == val) continue;
        // 纵向检查：当前格子的上边两个是否和当前尝试的 val 相同
        if (row >= 2 && grid[row - 2][col] == val && grid[row - 1][col] == val) continue;

        // --- 执行放置操作，并更新相关计数 ---
        grid[row][col] = val;
        if (val) {
            black_row[row]++;
            black_col[col]++;
        } else {
            white_row[row]++;
            white_col[col]++;
        }

        // --- 剪枝 3：如果当前放完了一整行或一整列，检查其唯一性 ---
        int flag = 1; // 标记是否通过唯一性检查
        string rowstr = "", colstr = "";
        int full_row = (col == 5); // 是否刚填完一行
        int full_col = (row == 5); // 是否刚填完一列

        if (full_row) {
            for (int i = 0; i < 6; i++) rowstr += to_string(grid[row][i]);
            if (vis_row.count(rowstr)) flag = 0; // 如果该行已出现过，则剪枝
            else vis_row.insert(rowstr); // 否则，将其加入已出现行的集合
        }
        if (full_col) {
            for (int i = 0; i < 6; i++) colstr += to_string(grid[i][col]);
            if (vis_col.count(colstr)) flag = 0; // 如果该列已出现过，则剪枝
            else vis_col.insert(colstr); // 否则，将其加入已出现列的集合
        }

        // 如果通过了所有剪枝，则递归地搜索下一个格子
        if (flag && solve(pos + 1)) return 1;

        // --- 回溯：撤销当前尝试的操作，恢复现场 ---
        if (full_row) vis_row.erase(rowstr);
        if (full_col) vis_col.erase(colstr);
        grid[row][col] = -1;
        if (val) {
            black_row[row]--;
            black_col[col]--;
        } else {
            white_row[row]--;
            white_col[col]--;
        }
    }
    return 0; // 如果当前格子尝试了两种颜色都无法得到解，则返回 0
}

int main() {
    // 程序开始前，先根据初始棋盘，初始化每行每列的黑白棋数量
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            if (grid[i][j] == 1) {
                black_row[i]++;
                black_col[j]++;
            } else if (grid[i][j] == 0) {
                white_row[i]++;
                white_col[j]++;
            }
        }
    }
    // 从第一个格子（编号 0）开始深度优先搜索
    if (solve(0)) {
        cout << ans << endl; // 输出最终找到的答案字符串
    }
    return 0;
}