C++-经典题目 八皇后

服务器管理 服务器管理 主题:1035 回复:2217

C++-经典题目 八皇后

偏爱自由 发布于 2017-06-20 字数 4354 浏览 1205 回复 1
//________________链表版八皇后
//修改 N 可以达到 N皇后 !!!
#include <iostream>
#include <vector>
#include <fstream>
#include <time.h>
using namespace std;
#define N 8
bool haha(int **a,int i,int j)
{

int i_1 = i;
int j_1 = j;
for(int x =0;x<N;x++)
{
if(j_1+x <N)
a[i_1][j_1+x]=0;
if(j_1-x>=0)
a[i_1][j_1-x]=0;
if(i_1+x <N)
a[i_1+x][j_1]=0;
if(i_1-x>=0)
a[i_1-x][j_1]=0;


}


for(int x =0;x<N;x++)
{
if(i_1+x<N&&j_1+x<N)
a[i_1+x][j_1+x]=0;
if(i_1+x<N&&j_1-x>=0)
a[i_1+x][j_1-x]=0;
}
for(int x =0;x<N;x++)
{
if(i_1-x>=0&&j_1-x>=0)
a[i_1-x][j_1-x]=0;
if(i_1-x>=0&&j_1+x<N)
a[i_1-x][j_1+x]=0;
}
a[i][j] = 1;
return true;

}
typedef struct hh_tree_{
int hh[N][N];
int x;
int y;
hh_tree_ *next;
}hh_tree,*phh_tree;
void deletenew(hh_tree_* tree)
{
hh_tree_ *temp = tree;
while(temp !=NULL)
{
tree = tree->next;
delete (hh_tree_*)temp;
temp = tree;

}
}
phh_tree bahuanghou(phh_tree ,phh_tree ,int);
int _tmain(int argc, _TCHAR* argv[])
{
clock_t tbegin,tend;
tbegin = ::clock();

int jishu =1;
for(int i_i = 0;i_i < N;i_i++)
{
phh_tree begin;
phh_tree end;
int hangshu = 0;
begin = new hh_tree;
for(int i = 0;i<N;i++)
for(int j = 0;j<N;j++)
(begin->hh)[i][j] = 3;

int *x[N];

for(int i = 0;i<N;i++)
x[i] = (begin->hh)[i];

haha(x,0,i_i);
begin->next = NULL;
begin->x =0;
begin->y =0;
end = begin;
for(int i = 0;i<N-1;i++)
{
begin = bahuanghou(begin,end,i);
phh_tree temp =begin;
while(temp != NULL)
{
temp = temp->next;
}
end = temp;
}

phh_tree temp =begin;
while(temp != NULL)
{
cout<<"_______________"<<jishu<<endl;
for(int i = 0;i<N;i++)
{
cout<<"n";
for(int j = 0;j<N;j++)
{
cout<<(temp->hh)[i][j]<<" ";
}
}
cout<<"_______________"<<endl;
temp = temp->next;
jishu++;
}
deletenew(begin);
begin = NULL;
end =NULL;
}
tend = ::clock();
cout<<(double)(tend-tbegin)/1000<<endl;
getchar();
return 0;
}
phh_tree bahuanghou(phh_tree begin,phh_tree end,int hangshu)
{
phh_tree be = begin;
hh_tree_ *tou = NULL;
hh_tree_ *wei = NULL;
hh_tree_ *sb = begin;
for(;be != NULL;)
{
for(int j = 0;j<N;j++)
{
if((be->hh)[hangshu+1][j] == 3)
{
hh_tree_ *node = new hh_tree_;
int *x[N];
for(int i_x = 0 ;i_x<N;i_x++)
for(int j_x = 0;j_x<N;j_x++)
{
node->hh[i_x][j_x]=be->hh[i_x][j_x];
}
node->next = NULL;
node->x = hangshu+1;
node->y = j;
for(int i = 0;i<N;i++)
x[i] = (node->hh)[i];
haha(x,hangshu+1,j);
if(tou == NULL)
{
tou = node;
wei = node;
}
else
{
wei->next = node;
wei = node;
}
}

}

if(tou ==NULL)
{
if(sb == begin &&be == begin)
{
begin = begin->next;
delete (hh_tree_*)be;
sb =begin;
be =begin;
tou = NULL;
wei = NULL;
continue;
}
else
{
sb->next = be->next;
delete (hh_tree_*)be;
be = sb;
tou = NULL;
wei = NULL;
}
}
else
{
if(be == begin)
{
wei->next = be->next;
delete (hh_tree_*)be;
begin = tou;
//temp_ = tou;
be = wei;
sb=wei;
tou = NULL;
wei = NULL;
}
else
{
wei->next = be->next;
sb->next = tou;
sb = wei;
delete (hh_tree_*)be;
be = wei;
tou = NULL;
wei = NULL;
}
}
be = be->next;
}
return begin;

}

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(1

瑾兮 2017-10-24 1 楼