问题标题: 酷町堂：4370 防盗（guard）

题目描述 Description

展台被分成N＊N个格子，某些格子中有钻石，为了防盗，需要建立防盗系统，防盗系统是一种光电检测装置，它可以检测它所在的行和列以及两个对角线共四条线上是否有人触碰。当然已经放置了钻石的位置是不能安装这个装置的，同时四条线上不能有多个装置，因为他们会互相干扰，发出错误的信号。针对以上防盗装置，我们想知道有多少种布局方案。

输入描述 Input Description

第一行一个整数N，表示展台的大小 接下来N行，每行N个0或1的整数，如果一个整数为0，表示对应的位置可以放防盗装置，如果一个整数为1，表示对应的位置放置了展品。

输出描述 Output Description

一个整数，表示总共有多少种放法。

样例输入 Sample Input

4

1 0 1 1

1 1 1 1

1 1 1 1

1 1 1 1

样例输出 Sample Output

1

数据范围及提示 Data Size & Hint

0＜N＜＝10

WA30

#include<iostream>
#include<bits/stdc++.h>
#pragma GCC optimize(3) 
using namespace std;
int cnt,n,ans;
bool vis[50];
bool a[50],b[50];
int c[50][50];
void dfs(int pos,int x){
	if(pos>x){
		cnt++;
		return ;
	} 
	for(int i=1;i<=n;i++){
		if(!vis[i]&&!a[pos-i+n-1]&&!b[pos+i]&&c[pos][i]==0){
			vis[i]=true;
			a[pos-i+n-1]=true;
			b[pos+i]=true;
			dfs(pos+1,x);
			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];
		}
	}
    for(int l=1;l<=n;l++){
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
        memset(b,0,sizeof(b));
        cnt=0;
        dfs(1,l);
        ans+=cnt;
    }
	cout<<ans;
	return 0;
}

汪恺恒在2021-04-06 19:22:02追加了内容

#include<iostream>
#include<bits/stdc++.h>
#pragma GCC optimize(3) 
using namespace std;
int n,ans;
bool vis[50];
bool a[50],b[50];
int c[50][50];
void dfs(int pos,int flag){
	if(pos>n){
		if(flag) ans++;
		return ;
	} 
	for(int i=1;i<=n;i++){
		if(!vis[i]&&!a[pos-i+10]&&!b[pos+i]&&c[pos][i]==0){
			vis[i]=true;
			a[pos-i+10]=true;
			b[pos+i]=true;
			dfs(pos+1,flag+1);
			vis[i]=false;
			a[pos-i+10]=false;
			b[pos+i]=false; 
		}
		if(i==n) dfs(pos+1,flag);
	}
	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,0);
	cout<<ans;
	return 0;
}