八皇后问题-DFS

2019-11-06 07:49:59

字体：大中小

来源：转载

供稿：网友

#include <stdio.h>#include <algorithm>#include <iostream>#include <math.h>#include <string>#include <cstring>#include <vector>using namespace std;int MAP[8][8];int hang[8];int lie[8];int z_xie[15];int c_xie[15];int sum=0;int dfs(int x){ if(x>7) { sum++; for(int i=0;i<8;i++) { for(int j=0;j<8;j++) cout<<MAP[i][j]<<" "; cout<<endl; } cout<<endl; return 1; //返回最近一次调用dfs的地方 } for(int y=0;y<8;y++) { if(MAP[x][y]==1) dfs(x+1); if(!hang[x]&&!lie[y]&&!z_xie[x-y+7]&&!c_xie[x+y]) //重点 {

MAP[x][y]=1;

hang[x]=1; lie[y]=1; z_xie[x-y+7]=1; c_xie[x+y]=1; dfs(x+1); MAP[x][y]=0; hang[x]=0; lie[y]=0; z_xie[x-y+7]=0; c_xie[x+y]=0; } } return sum; //返回到主函数}int main(){ int s=dfs(0); cout<<"the sum is:"<<s<<endl; return 0;}

上一篇：leetcode - 36.Valid Sudoku

下一篇：粒子群优化算法介绍