题目描述

给定$n\times n$的棋盘，*表示可放，.表示不可放，每行放一个棋子，要求不能有两个及以上的棋子出现在同一列上（即每一列只能放一个），请问有多少种放置的方法？

输入输出格式

输入

一行，一个整数$n$。接下来$n$行，每行$n$个字符，表示棋盘。

输出

一个整数，表示方案总数

样例

#1
4
****
****
****
****

#2
4
**.*
*.*.
**..
****

#1
24

#2
5

说明提示

$1\leq n\leq 11$

（我60分TLE）代码：

#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;

int cnt = 0;

void dfs(char *b, int *v, int n, int d) {
    if (d == n) {
        set<int> s;
        pair<set<int> :: iterator, bool > r;
        for (int i = 0; i < n; i ++) {
            r = s.insert(v[i]);
            if (!r.second) {
                return;
            }
        }
        cnt ++;
        return;
    }
    for (v[d] = 0; v[d] < n; v[d] ++) {
        if (* (b + n * d + v[d]) == '*') {
            dfs(b, v, n, d + 1);
        }
    }
}

int main() {
    int n;
    cin >> n;
    int v[n];
    char b[n][n];
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            cin >> b[i][j];
        }
    }
    dfs(*b, v, n, 0);
    cout << cnt << '\n';
    return 0;
}