问题标题: 酷町堂：6509 布阵

题目描述 Description

国王要求军师布一个阵，需要将M个士兵布置在一个M*M的矩阵上，矩阵由 “*” 和 “.” 组成，"*" 表示该位置可以布置士兵，"." 表示该位置不能布置士兵。
布置完成后，要求矩阵的每一行、每一列最多只有一个士兵，矩阵的对角线以及与两条对角线平行的线上最多只能有一个士兵。
请你找出所有布阵的方式，输出布阵方式的总数。

输入描述 Input Description

第一行一个整数M。
接下来M*M的矩阵，“*”表示可布置士兵“.”表示不能布置士兵。

输出描述 Output Description

一个整数表示解的总数

样例输入 Sample Input

4

**.*

****

****

****

样例输出 Sample Output

1

初看题目，还以为就是个dfs八皇后，结果测评结果令人大跌眼镜……

爆TLE90

#include<iostream>
using namespace std;
int cnt,n;
bool vis[50];
bool a[50],b[50];
char c[50][50];
void dfs(int pos){
	if(pos>n){
		cnt++;
		return ;
	} 
	for(int i=1;i<=n;i++){
		if(!vis[i]&&!a[pos-i+n-1]&&!b[pos+i]&&c[pos][i]=='*'){
			vis[i]=true;
			a[pos-i+n-1]=true;
			b[pos+i]=true;
			dfs(pos+1);
			vis[i]=false;
			a[pos-i+n-1]=false;
			b[pos+i]=false; 
		}
	}
	return ;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>c[i][j];
		}
	}
	dfs(1);
	cout<<cnt;
	return 0;
}

求优化（难道真要用什么位运算？）

汪恺恒在2021-05-10 19:05:15追加了内容

d