1114棋盘问题acwing（深度优先搜索）

题目描述

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。

要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 kk 个棋子的所有可行的摆放方案数目 CC。

输入格式

输入含有多组测试数据。

每组数据的第一行是两个正整数 n,kn,k，用一个空格隔开，表示了将在一个 n∗nn∗n 的矩阵内描述棋盘，以及摆放棋子的数目。当为-1 -1时表示输入结束。

随后的 nn 行描述了棋盘的形状：每行有 nn 个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出格式

对于每一组数据，给出一行输出，输出摆放的方案数目 CC （数据保证 C<231C<231）。

数据范围

n≤8,k≤nn≤8,k≤n

输入样例：

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

输出样例：

2
1

代码如下：

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

// 全局变量声明
int res = 0;            // 结果，存储可行方案数目
int nn = 0, number = 0; // nn为棋盘大小n，number为需要放置的棋子数k
vector<bool> v;         // 标记列是否被占用，v[i]为true表示第i列已被使用
vector<vector<char>> b; // 棋盘，存储'#'和'.'，b[x][i]表示第x行第i列

// 深度优先搜索函数
// 参数x：当前处理的行号，count：已放置的棋子数目
void dfs(int x, int count) {
    // 如果已放置number个棋子，方案数+1并返回
    if (count == number) {
        res++;
        return;
    }
    // 若超出棋盘行数，直接返回
    if (x > nn) {
        return;
    }
    // 遍历当前行的所有列，尝试放置棋子
    for (int i = 1; i <= nn; i++) {
        // 如果当前列未被占用且该位置可放置
        if (!v[i] && b[x][i] == '#') {
            v[i] = true;           // 标记该列为已使用
            dfs(x + 1, count + 1); // 递归处理下一行，棋子数+1
            v[i] = false;          // 回溯，撤销列的标记
        }
    }
    // 不放置当前行的棋子，直接处理下一行
    dfs(x + 1, count);
}

int main() {
    // 循环处理多组输入，直到输入-1 -1为止
    while (1) {
        cin >> nn >> number;
        if (nn == -1 && number == -1)
            break;
        // 初始化棋盘和标记数组
        b.assign(nn + 1, vector<char>(nn + 1, 0));
        v.assign(nn + 1, false);
        // 读取棋盘数据，注意行和列从1开始存储
        for (int i = 1; i <= nn; i++) {
            for (int j = 1; j <= nn; j++) {
                cin >> b[i][j];
            }
        }
        res = 0;            // 重置结果
        dfs(1, 0);           // 从第1行开始搜索，初始已放置0个棋子
        cout << res << endl; // 输出当前棋盘的方案数
    }
    return 0;
}

/*
思路详解：
1. **问题分析**：在n×n棋盘的'#'位置放置k个棋子，要求任意两个棋子不同行不同列。需要计算所有可行方案数。
2. **搜索策略**：采用深度优先搜索（DFS）逐行处理，每行有两种选择：放置或不放置棋子。
3. **放置规则**：
   - 在当前行选择一个未被占用的列（对应'#'位置）。
   - 标记该列，递归处理下一行。
   - 回溯时撤销列的标记，以尝试其他可能的列。
4. **剪枝与终止条件**：
   - 当已放置k个棋子时，方案数+1。
   - 当处理完所有行时终止当前路径。
5. **复杂度优化**：逐行处理避免行冲突，列标记数组避免列冲突，确保每行每列最多一个棋子。
6. **递归过程**：每次递归处理下一行，确保行号递增，从而覆盖所有行选择组合。
*/

代码说明

1. DFS 递归搜索
   • 遍历当前行 x 的所有列，如果当前格子是 # 且该列未被占用，就放置棋子，并递归搜索下一行。
   • 不放置棋子，直接跳到下一行，保证搜索完整棋盘。
2. 回溯
   • 递归调用 dfs(x+1, count+1); 进入下一行。
   • 递归返回后，取消该列的占用状态（v[i] = false;），以便尝试其他方案。
3. 终止条件
   • 棋子数量等于 k：找到一种有效方案，res++ 并返回。
   • 超出行界限 x > n：无效路径，直接返回。

时间复杂度分析

最坏情况下，n=8，k=8，即 8! ≈ 40,320，这种规模可以接受。