一个有趣的警示后人
查看原帖
一个有趣的警示后人
1252442
lucy2012楼主2024/8/29 15:16

如果你是暴力请看,如果想ac请左转题解区,本题正解位运算。

这样是70分:

#include<bits/stdc++.h>
using namespace std;
char ch[20][20];
int n,vy[20],di[2][100],ans;
void dfs(int deep){
	if(deep==n+1){
		ans++;
		return;
	}
	for(int i=1;i<=n;i++){
		if(!vy[i]&&!di[0][i+deep]&&!di[1][i-deep+15]&&ch[deep][i]!='.'){
			vy[i]=di[0][i+deep]=di[1][i-deep+15]=1;
		    dfs(deep+1);
		    vy[i]=di[0][i+deep]=di[1][i-deep+15]=0;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>ch[i][j];
		}
	}
	dfs(1);
	cout<<ans;
	return 0;
}

而这样可以拿到80分:

#include<bits/stdc++.h>
using namespace std;
char ch[20][20];
int n,vy[20],di[2][100],ans;
void dfs(int deep){
	if(deep==n+1){
		ans++;
		return;
	}
	for(int i=1;i<=n;i++){
		if(vy[i]||di[0][i+deep]||di[1][i-deep+15]||ch[deep][i]=='.')//注意是这里改进了
		    continue;
		vy[i]=di[0][i+deep]=di[1][i-deep+15]=1;
		dfs(deep+1);
		vy[i]=di[0][i+deep]=di[1][i-deep+15]=0;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>ch[i][j];
		}
	}
	dfs(1);
	cout<<ans;
	return 0;
}

60分是怎么拿到的我真的不知道了QwQ,本人第一次拿了80分,看见题解区大佬60分错误代码是上面两个代码的差距,但是自己手改后亲测70分,不知道60分是怎么打的awa。

2024/8/29 15:16
加载中...