传送门：poj3239
其实这个题深搜（n>25基本就崩的差不多了）是过不了的。。想过只能套公式，构造公式法详见：http://blog.csdn.net/lyy289065406/article/details/6642789
之所以写深搜是因为推导不出来公式，套用网上现成的公式又没多大意思，不如练一练搜索。
深搜还是老套路，依然需要注意的就是标记的复位问题，还有就是这个题要注意皇后之间的斜率不能为±1。
#include<stdio.h> #include<math.h> #include<algorithm> #include<string.h> using namespace std; int n; struct node { int c,r; }m[303]; int book[303]; int dfs(int r,int x)//参数为当前行数和已放置的皇后的个数 { if(x==n) return 1; int flag=0; for(int i=1;i<=n;i++)//枚举每一列 { flag=0; for(int j=1;j<=x;j++)//枚举每个已放置的皇后 { if(abs(m[j].c-i)==abs(r-m[j].r))//判断和前面已放置的皇后的斜率是不是±1 { flag=1; break; } } if(!flag&&!book[i])//如果当前列可以放置皇后 { book[i]=1; m[x+1].c=i; m[x+1].r=r; int f=dfs(r+1,x+1); if(f)//如果采取上面的放置方法后面无法继续放完要把当前位置标记取消 return 1; else book[i]=0; } } return 0; } int main() { while(scanf("%d",&n)&&n) { dfs(1,0); memset(book,0,sizeof(book)); for(int i=1;i<=n;i++) printf("%d ",m[i].c); putchar('\n'); } }
