dfs(暴力枚举) $O(n^2)$
这题的方案数相当于是求组合数问题
但是带行列限制 不然可以直接输出组合数了
试图利用这个优化 但是看起来挺失败的 699ms
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 10;
int n, k;
//存储可以放棋子的地方的坐标
PII g[N * N];
//z是g的数组长度
int z, cnt;
bool st[N * N], cols[N], rows[N];
void dfs(int u, int h)
{
if(u == k)
{
cnt++;
return;
}
//h是这个状态的最高位 因为是排列数所以比他低的用不上
for(int i = h; i<z; i++)
{
if(st[i] || cols[g[i].first] || rows[g[i].second])
{
continue;
}
//显而易见的判断、选择和回溯了
st[i] = cols[g[i].first] = rows[g[i].second] = true;
dfs(u + 1, i);
st[i] = cols[g[i].first] = rows[g[i].second] = false;
}
}
int main()
{
while(scanf("%d %d", &n, &k), n != -1 && k != -1)
{
z = cnt = 0;
for(int i = 0; i<n; i++)
{
getchar();
for(int j = 0; j<n; j++)
{
char t = getchar();
//只需要棋盘区域的坐标 空白区域用不上
if(t == '#')
{
g[z++] = {i, j};
}
}
}
dfs(0, 0);
printf("%d\n", cnt);
}
}