M01321: 棋盘问题

backtracking, http://cs101.openjudge.cn/pctbook/M01321

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

输入

输入含有多组测试数据。每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出

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

样例输入

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

样例输出

2
1

来源

蔡错@pku

这个问题要求我们在一个不规则的棋盘上摆放棋子，且任何两个棋子都不能放在同一行或同一列。我们需要找出所有符合条件的摆放方案数。

思路分析：

棋盘的表示： 棋盘是一个n*n的矩阵，每个位置上可能是#（可以放棋子）或者.（不能放棋子）。
摆放棋子的要求：
- 不同的棋子不能在同一行或同一列。
- k个棋子必须放置在#的位置上。
求解方法： 这类似于n皇后问题的变种，可以使用回溯法来搜索所有可行的摆放方案。
回溯法：
- 通过回溯的方法尝试在棋盘上放置k个棋子。
- 需要记录已被放置棋子的行和列，避免放在同一行或同一列。
- 只考虑可以放棋子的格子，即#的位置。
输入与输出：
- 输入中有多组测试数据，直到输入为-1 -1时结束。
- 对每组数据输出可行的摆放方案数。

cpp

#include <iostream>
#include <vector>

using namespace std;

// 回溯函数
void placePieces(int n, int k, int row, vector<string>& board, vector<int>& cols, int& count) {
    // 如果已经放置了k个棋子，计数加一
    if (k == 0) {
        count++;
        return;
    }
    
    // 从当前行row开始尝试
    for (int i = row; i < n; i++) {
        // 遍历该行所有列
        for (int j = 0; j < n; j++) {
            // 如果当前位置是可放棋子的地方，并且没有放置在该列，且该行还没被用过
            if (board[i][j] == '#' && !cols[j]) {
                // 放置棋子，标记该行和该列
                cols[j] = 1;
                placePieces(n, k - 1, i + 1, board, cols, count);
                // 回溯，撤销棋子的放置
                cols[j] = 0;
            }
        }
    }
}

int main() {
    int n, k;
    
    while (cin >> n >> k, n != -1 && k != -1) {
        vector<string> board(n);
        for (int i = 0; i < n; i++) {
            cin >> board[i];
        }
        
        vector<int> cols(n, 0);  // 用来记录列的状态，0表示该列没有放棋子，1表示放了
        int count = 0;
        
        placePieces(n, k, 0, board, cols, count);
        
        cout << count << endl;
    }
    
    return 0;
}

代码解释：

placePieces函数：
- 这是一个回溯函数，用来递归地在棋盘上放置k个棋子。
- 参数：
  - n：棋盘的大小。
  - k：当前需要放置的棋子数目。
  - row：当前正在处理的行。
  - board：棋盘的形状，记录每个位置是否可放棋子。
  - cols：一个数组，用来标记哪些列已经被占用。
  - count：用来记录当前的方案数。
- 回溯的核心是：在一个行内，尝试将棋子放在每个#的位置上，放置棋子后递归处理下一个棋子，放置后回溯撤销该放置，继续寻找下一个位置。
main函数：
- 读取输入，处理每一组测试数据。
- 对于每组数据，调用placePieces函数来计算所有可能的摆放方案数。

时间复杂度：

由于最多有n行，每行最多有n个格子需要判断，递归过程中最多会遍历所有可能的放置方式。
回溯的时间复杂度大致为O(n^k)，其中k是要摆放的棋子数。

M01321: 棋盘问题 ​

M01321: 棋盘问题