BZOJ P4809 皇后

    xiaoxiao2021-03-25  287

    非常裸的n皇后问题,

    爆搜水过

    但是讲道理这题真的要考的应该不是爆搜,应该是DLX或者A*吧

    下面代码

    #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,ans; bool r[20],x1[37],x2[37]; int a[20][20]; void dfs(int x){ if(x==n+1){ ans++; return; } for(int i=1;i<=n;i++){ if(!a[x][i]&&r[i]+x1[x-i+n]+x2[x+i]==0){ r[i]=true; x1[x-i+n]=true; x2[x+i]=true; dfs(x+1); r[i]=false; x1[x-i+n]=false; x2[x+i]=false; } } return; } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[i][j]; } } dfs(1); cout<<ans<<endl; return 0; } /* in: 4 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 out: 1 */

    转载请注明原文地址: https://ju.6miu.com/read-149.html

    最新回复(0)