如果你是暴力请看,如果想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。