题目描述

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

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

样例

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

2
1

算法

DFS

1. 因为输入格式给定了棋盘的样式，所以先输入图g[N][N]
2. 接下来，就是dfs(u, s)；u表示行号，s表示当前棋子个数。dfs(u, s)的行是第0行，当前有0个棋子，所以是dfs(0, 0)。
3. dfs(u, v)的一开始，是判断s == k，也就是这一层递归中，棋子数是否达到了标准k个，如果达到了，就return 1。
4. 然后判断u == n，如果到了第u行，棋子个数还没满足k的话，那么说明这个方案不合法，我们则return 0。
5. 接下来，则是开始递归搜索树的过程。

   • 首先不放也算一种方案，所以直接递归到下一行，棋子数s不增加。int res = dfs(u + 1, s)
   • 枚举一下当前这行u中，哪些列可以放棋子。 res += dfs(u + 1, s + 1)

6. 要记得“恢复现场”，在“对称”的位置。
7. 最后return res。

时间复杂度

因为我们是按行枚举，所以时间复杂度是$O(n!)$

C++ 代码

#include <iostream>

using namespace std;

const int N = 10;

int n, k;
char g[N][N];
bool st[N];   // 使用st[N]数组表示哪些列已经被占用了
int res;

int dfs(int u, int s)
{
    if(s == k) return 1;  // 如果当前棋子数已经满足条件k，说明方案合法，返回1 
    if(u == n) return 0;  // return -1 // 如果已经走到了第n行，但是没有凑够棋子，表明当前方案不合法，返回0

    // 表示这一行可以不放棋子，直接下一行
    int res = dfs(u + 1, s);

    // 枚举以下，当前这行中，哪些列可以放棋子
    for(int i = 0; i < n; i ++)
    {
        /*
        if(!st[u] && g[u][i] == '#')
        {
            st[u] = true;

            // if(s < k) return res += dfs(u + 1, s + 1);
            res += dfs(u + 1, s + 1);

            st[u] = false;
            s --;                                               // **2
        }
        */

        if(!st[i] && g[u][i] == '#') // **1
        {
            // 将当前这列标记一下，表示它已经被用过了
            st[i] = true;
            res += dfs(u + 1, s + 1);
            st[i] = false;
        }
    }

    return res;
}

int main()
{
    // while(cin >> n >> k, n || k)
    while(cin >> n >> k, n != -1 || k != -1)
    {
        for(int i = 0; i < n; i ++) cin >> g[i];

        cout << dfs(0, 0) << endl; // 从第0行开始看，有0个棋子数量的方案数
    }

    return 0;
}

问题

1. 写while(cin >> n >> k, n || k)会MLE，不知道为什么
2. 为什么把不放棋子的dfs()放在最前面
3. 判断st[N]中，是st[i]，也就是每一列st[i]，而不是每一行st[u]，因为我们dfs()中，就在当前行。
4. 之前疑惑为什么恢复现场的时候不进行 s --，现在想想，应该是恢复现场的时候，当前dfs()中的s并没有+1，只是st[i]变了而已，所以恢复st[i] = false这一个就够了。
5. 时间复杂度的分析还不够熟练，如果$O(n!)$错了的话，希望大家指出来hh。