主题:采用递归调用putchess函数的方法编程八皇后
雕刻
[专家分:0] 发布于 2005-12-28 22:54:00
求助各位大虾,采用递归调用putchess函数的方法编程八皇后,
要求:要在语句中有解释说明,以及参考的资料,自己这么设计的想法及感受,要在C或C++中实现。
急用啊,有的给我发到zhhgd605@126.com
我在此先谢过大家了
[em21][em21][em21][em21][em21]
4 楼
紫忆 [专家分:2480] 发布于 2005-12-30 13:25:00
很久以前编的迷宫'E是入口,S是出口'
#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
#define N 8
/////////////////////算法一:
typedef struct stack{
int I;
int J;
int step;//步数
stack *next;
}STACK;
STACK *top;
STACK* InitStack()
{
top=(STACK *)malloc(sizeof(STACK));
top->next=NULL;
top->step=0;
return top;
}
void push(int i,int j)
{
STACK *p;
p=(STACK *)malloc(sizeof(STACK));
p->I=i;
p->J=j;
p->next=top->next;
top->next=p;
top->step++;
}
int pop(int &i,int &j)
{
STACK *p;
if(top->next){
p=top->next;
top->next=p->next;
}
else if(top->next==NULL)
return 0;
i=p->I;
j=p->J;
top->step--;
return 1;
}
int ok(char a[][N],int i,int j)
{
while((i<N&&i>=0)&&(j<N&&j>=0)){
if(a[i][j]=='S'){//找到出口
break;
}
if(a[i-1][j]!='X'&&a[i-1][j]!='Y'){ //上边不是墙且不是死路,并且没有走过则压栈
a[i][j]='X';//经过该点则标记,否则在N000 处会造成原路返回结果
push(i,j); // 000S
i=i-1;
continue;
}
if(a[i+1][j]!='X'&&a[i+1][j]!='Y'){//下
a[i][j]='X';
push(i,j);
i=i+1;
continue;
}
if(a[i][j-1]!='X'&&a[i][j-1]!='Y'){//左
a[i][j]='X';
push(i,j);
j=j-1;
continue;
}
if(a[i][j+1]!='X'&&a[i][j+1]!='Y'){//右
a[i][j]='X';
push(i,j);
j=j+1;
continue;
}
//四个方向都不通
a[i][j]='Y';//Y表示此路已经走过但是不通,否则会在该处造成无限循环
int s;
s=pop(i,j);
if(!s)
return 0;
}
return 1;
}
int main(int argc, char* argv[])
{
char a[N][N]={ 'X','X','X','X','X','X','X','X',\
'X','E','0','0','X','S','X','X',\
'X','X','0','X','0','X','X','X',\
'X','0','0','0','0','X','0','X',\
'X','X','X','X','0','0','0','X',\
'X','0','0','0','0','X','X','X',\
'X','X','X','X','0','X','X','X',\
'X','X','X','X','X','X','X','X',};
int i,j,i0,j0;
InitStack();
for(i=0;i<N;i++){
for(j=0;j<N;j++)
if(a[i][j]=='E'){
i0=i;
j0=j;
}
}
int s;
s=ok(a,i0,j0);
if(!s){
printf("迷宫走不通");
exit(0);
}
printf("%d步可以走出迷宫",top->step);
while(top->next){
pop(i,j);
a[i][j]='*';
}
for(i=0;i<N;i++){
printf("\n");
for(j=0;j<N;j++){
if(a[i][j]=='Y')//将Y还原
a[i][j]='0';
printf("%c",a[i][j]);
}
}
return 0;
}