BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（初中组） 第 21 题

4.

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

int a[6][6], s[6];
bool v[6], f;

void dfs(int x)
{
    if (x == 6)
    {
        f = 1;
        for (int i = 1; i <= 5; i++)
            cout << char(s[i] + 'A' - 1) << ' ';
        cout << endl;
    }
    else
    {
        for (int i = 1; i <= 5; i++)
        {
            if (a[x][i] == 1 && v[i] == 0)
            {
                s[x] = i;
                v[i] = 1;
                dfs(x + 1);
                v[i] = 0;
            }
        }
        return ;
    }
}

int main()
{
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            cin >> a[i][j];

    dfs(1);
    if (f == 0)
        cout << "no";
    return 0;
}

输入：

1 0 1 1 0
0 0 0 0 1
0 0 1 0 1
1 1 0 1 1
0 0 0 1 0

输出：（ ）

这题考的是回溯法求全排列。拿到题别慌，先看 dfs 里的递归结构：x 从 1 到 5 依次填列，a[x][i] 是 1 才允许选第 i 行，v[i] 标记行是否被用过。核心就是模拟这个搜索树，把合法路径输出。

最容易犯的错是只盯着输入矩阵看，忘了 v 数组的作用——它保证每一行只能用一次，否则你会得到重复的列组合。另外，很多同学会以为只要 a[x][i]==1 就能直接选，忽略了递归返回后要把 v[i] 恢复成 0，否则下一层会误以为这行还能用。还有一个隐蔽坑：题目给的输入是 5 行 5 列，但输出要按列顺序打印（第 1 列到第 5 列），别把行列搞反了。最后，别忘了 f 标志位，如果搜完所有分支都没找到合法解，程序会输出"no"，但本题一定有解，所以不用处理。

这道题考查的是回溯法（深度优先搜索）在排列问题中的应用，属于 CSP-J/S 中非常经典的算法模型。命题人喜欢用这种"带约束的排列"来挖坑，因为表面上看只是遍历，实际上对状态管理的要求很高。学生拿到题，首先要读懂代码的逻辑骨架。

先看主函数：读入一个 5×5 的 0/1 矩阵 a，然后调用 dfs(1)。这里的 a[i][j] 表示第 i 列能否选第 j 行。再看看 dfs 函数：参数 x 代表当前要填第几列（从 1 到 5）。当 x==6 时，说明前 5 列都填好了，此时 f=1 表示找到了合法路径，然后按顺序输出 s[1]~s[5] 对应的字母（s[i] 存的是第 i 列选的行号，减去 1 再转成字符）。如果 x<6，就枚举 i 从 1 到 5：只有当 a[x][i]==1 且 v[i]==0 时才递归。这里 v 数组就是关键——它标记了某一行是否已经被前面的列选走了，保证每行最多出现一次。

现在代入题目给的输入矩阵： 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0

我们手动模拟一下搜索过程，这是解题的核心心法：

第一步，x=1，枚举 i=1~5。a[1][1]=1 且 v[1]=0，所以选 i=1，s[1]=1，v[1]=1，递归 dfs(2)。 第二步，x=2，枚举 i=1~5。a[2][1]=0 跳过；a[2][2]=0 跳过；a[2][3]=0 跳过；a[2][4]=0 跳过；a[2][5]=1 且 v[5]=0，所以选 i=5，s[2]=5，v[5]=1，递归 dfs(3)。 第三步，x=3，枚举 i=1~5。a[3][1]=0；a[3][2]=0；a[3][3]=1 但 v[3]=0 可用？等等，v[3] 还没被用过，但 a[3][3]=1 意味着第 3 列选第 3 行，行 3 目前未被使用，所以可以选？不对，我们再仔细看：a[3][3]=1，v[3]=0，所以选 i=3，s[3]=3，v[3]=1，递归 dfs(4)。 第四步，x=4，枚举 i=1~5。a[4][1]=1 但 v[1]=1 已用；a[4][2]=1 且 v[2]=0，所以选 i=2，s[4]=2，v[2]=1，递归 dfs(5)。 第五步，x=5，枚举 i=1~5。a[5][1]=0；a[5][2]=0；a[5][3]=0；a[5][4]=1 但 v[4]=0？等等，v[4] 还没被用过，但 a[5][4]=1 意味着第 5 列选第 4 行，行 4 未被使用，所以可以选？不对，我们再检查：a[5][4]=1，v[4]=0，所以选 i=4，s[5]=4，v[4]=1，递归 dfs(6)。 第六步，x=6，输出 s[1]~s[5]：1,5,3,2,4 对应字母 C,B,A,D,E？等等，这里我好像算错了，重新核对每一步的选择是否正确。

重新仔细模拟一遍，确保每一步都符合 a[x][i]==1 且 v[i]==0： x=1: a[1][1]=1, v[1]=0 → 选 1, v[1]=1 x=2: a[2][1]=0, a[2][2]=0, a[2][3]=0, a[2][4]=0, a[2][5]=1, v[5]=0 → 选 5, v[5]=1 x=3: a[3][1]=0, a[3][2]=0, a[3][3]=1, v[3]=0 → 选 3, v[3]=1 x=4: a[4][1]=1, v[1]=1(已用), a[4][2]=1, v[2]=0 → 选 2, v[2]=1 x=5: a[5][1]=0, a[5][2]=0, a[5][3]=0, a[5][4]=1, v[4]=0 → 选 4, v[4]=1 x=6: 输出 1,5,3,2,4 → C,B,A,D,E？不对，字母转换：1→A, 2→B, 3→C, 4→D, 5→E。所以输出 A E C D B？等等，我再检查选项：A. C B E A D, B. A E C D B, C. C A E D Q, D. A E C B D。

显然我刚才的模拟结果 A E C D B 对应选项 B，但正确答案是 D，说明我在某一步选错了。回溯一下：x=4 时，a[4][1]=1 但 v[1]=1 已用，a[4][2]=1 且 v[2]=0，所以选 2 是对的。x=5 时，a[5][4]=1 且 v[4]=0，选 4 也是对的。那问题出在哪？哦，x=3 时，a[3][3]=1 且 v[3]=0，选 3 是对的。x=2 时，a[2][5]=1 且 v[5]=0，选 5 是对的。x=1 时，a[1][1]=1 且 v[1]=0，选 1 是对的。这样得到的序列确实是 1,5,3,2,4 → A E C D B，对应选项 B。但题目说正确答案是 D，难道我读错矩阵了？再看输入： 1 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0

等等，x=3 时，a[3][3]=1，但 v[3]=0，选 3 是对的。x=4 时，a[4][1]=1 但 v[1]=1，a[4][2]=1 且 v[2]=0，选 2 是对的。x=5 时，a[5][4]=1 且 v[4]=0，选 4 是对的。这样得到的序列确实是 1,5,3,2,4 → A E C D B。但正确答案是 D，说明我可能在某一步漏掉了其他分支？或者题目给的正确答案有误？再仔细看选项 D：A E C B D，对应行号 1,5,3,2,4？不对，D 是 A E C B D，行号 1,5,3,2,4？等等，字母转换：A=1, E=5, C=3, B=2, D=4。所以 D 对应 1,5,3,2,4，和我模拟的一样。哦！原来选项 D 就是 A E C B D，对应行号 1,5,3,2,4。我刚才误以为选项 D 是别的顺序。所以正确答案确实是 D。