百练 2754 八皇后 DFS经典题，递归，枚举

开始研究DFS好久也只弄懂个大概。。。。回溯是个问题。。。。
模拟起来总是有一定难度 = =！！
后来想一下，好像弄个全排列时间复杂度也不是很大啊。。。
试试枚举 = =
手写半小时，0ms AC....
囧~


代码水的可以。。。 = =
直接打表水过去了。。。。


#include”cstdio“
#include”algorithm“
#include”cmath“
#include“memory.h”
using namespace std;
int queen[8]={1,2,3,4,5,6,7,8};
int res[92][8];
int main()
{
int i = 0,j,k;
while(next_permutation(queen,queen + 8)){
for(j = 0;j < 7;j ++){
for(k = j + 1;k < 8;k ++)
if(abs(queen[j] - queen[k]) == abs(j - k))break;    //在对角线上
if(k != 8)break;
}
if(j == 7 && i < 92){
memcpy(res[i],queen,sizeof(queen));
i ++;
}
}
scanf("%d",&i);
while(i --){
scanf("%d",&j);
for(k = 0;k < 8;k ++)
printf("%d",res[j - 1][k]);
printf("\n");
}
return 0;
}




随后贴上DFS代码。。。。
导引上的解法，加了调试程序细心看了一次
感觉上效率不算太高。虽然模拟的过程是不错的，思想是值得学习的

#include“stdio.h”
#include“math.h”
#include“cstdlib”
int queenPlaces[92][8]; //存放92 种皇后棋子的摆放方法
int count = 0;
int board[8][8]; //仿真棋盘
void putQueen(int ithQueen); //递归函数，每次摆好一个棋子
int main()
{
int n, i, j;
for(i = 0; i < 8; i++){ // 初始化
for(j = 0; j < 8; j++)
board[i][j] = -1;
for(j = 0; j < 92; j++)
queenPlaces[j][i] = 0;
}
putQueen(0); //从第0 个棋子开始摆放，运行的结果是将queenPlaces 生成好
scanf("%d", &n);
for(i = 0; i < n; i++){
int ith;
scanf("%d", &ith);
for(j = 0; j < 8; j++)
printf("%d", queenPlaces[ith - 1][j]);
printf("\n");
}
return 0;
}
void putQueen(int ithQueen)
{
int i, k, r;
if(ithQueen == 8){
count ++;
return;
}
for(i = 0; i < 8; i++){
if(board[i][ithQueen] == -1){
//摆放皇后
board[i][ithQueen] = ithQueen;
//将其后所有的摆放方法的第ith 个皇后都放在i+1 的位置上
//在i 增加以后，后面的第ith 个皇后摆放方法后覆盖此时的设置
for(k = count; k < 92; k++)
queenPlaces[k][ithQueen] = i + 1;
//设置控制范围
for(k = 0; k < 8; k++)
for(r = 0; r < 8; r++)
if(board[k][r] == -1 && (k == i || r == ithQueen || abs(k - i) == abs(r - ithQueen)))
board[k][r] = ithQueen;


/*调试程序
for(k = 0; k < 8; k++){
for(r = 0; r < 8; r++)
printf("%3d",board[k][r]);
printf("\n");
}
system("pause");
system("cls");
*/


//向下级递归
putQueen(ithQueen + 1);
//回溯，撤销控制范围
for(k = 0; k < 8; k++)
for(r = 0; r < 8; r++)
if(board[k][r] == ithQueen) board[k][r] = -1;


/*调试程序
for(k = 0; k < 8; k++){
for(r = 0; r < 8; r++)
printf("%3d",board[k][r]);
printf("\n");
}
system("pause");
system("cls");
*/


}
}
}