#include <iostream>
using namespace std;
struct stack
{
int x;
int y;
int NextStep;//下一步
int CallOrder[8];//访问顺序
struct stack *back;
};
const int N=8;
int board[N][N];
int try1[]={-2,-1,1,2,2,1,-1,-2};
int try2[]={1,2,2,1,-1,-2,-2,-1};
int GetValue(const int x,const int y) //取x,y的权值
{
int count=0,i,x1,y1;
for(i=0;i<N;i++)
{
x1=x+try1[i];
y1=y+try2[i];
if(x1>=0&&x1<N&&y1>=0&&y1<N&&!board[x1][y1])
count++;//如果点落在棋盘内,则权值加1
}
return count;
}
/*进栈*/
stack *push(const int x,const int y,stack *top,const int NextStep)
{
stack *p=new stack;
int x1,y1,i,j,k=0;
int values[N];
//取得各点权值
for(i=0;i<N;i++)
{
x1=x+try1[i];
y1=y+try2[i];
if(x1<0||x1>N-1||y1<0||y1>N-1||board[x1][y1])
values[i]=-1;//该位置不能踏,权值减1
else
values[i]=GetValue(x1,y1);
}
//对values进行排序
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
if(values[j]==i)
p->CallOrder[k++]=j;
}
p->CallOrder[k]=-1;
p->x=x;
p->y=y;
p->NextStep=NextStep;
p->back=top;
return p;
}
//出栈
stack *pop(stack *top,stack& work)
{
work=*top;
top=top->back;
return top;
}
/*输入起始位置*/
void input(int& x,int& y)
{
while(1)
{
cout<<"请输入马的起始“行”坐标:(1~8)";
cin>>x;
cout<<"请输入马的起始“列”坐标:(1~8)";
cin>>y;
if(x>0&&x<=N&&y>0&&y<=8)
{
x-=1;
y-=1;
break;
}
}
}
void output()//输出
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
if(board[i][j]<10)
cout<<" "<<board[i][j]<<" ";
else
cout<<" "<<board[i][j];
cout<<endl;
}
}
void initialize()//初始化
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
board[i][j]=0;
}
/*主函数*/
void main()
{
cout<<"********************************************************************************";
cout<<"***************************欢迎使用马踏棋盘算法程序*****************************";
cout<<"********************************************************************************";
cout<<"******************************** 进入程序请按 a ********************************";
cout<<"********************************************************************************";
void output();
/*界面选择*/
char put;
ab:cin>>put;
if(put!='a')
{
cout<<"输入错误,请重新输入!";
goto ab;
}
cd:void input(int&,int&);
void initialize();
int count=1;
int i,x1,y1;
stack *top=NULL,work;
input(x1,y1);//输入起始位置
initialize();//初始化
board[x1][y1]=count++;
top=push(x1,y1,top,0);
while(1)
{
top=pop(top,work);
for(i=work.NextStep;i<N&&work.CallOrder[i]!=-1;)
{
x1=work.x+try1[work.CallOrder[i]];
y1=work.y+try2[work.CallOrder[i]];
top=push(work.x,work.y,top,i+1);
board[x1][y1]=count++;
work.x=x1;
work.y=y1;
i=0;
top=push(x1,y1,top,0);
top=pop(top,work);
}
if(count>N*N)
break;
board[x1][y1]=0;
count--;//回溯
}
cout<<endl;
cout<<"棋盘如下,走法按数字顺序"<<endl;
cout<<endl;
cout<<" 1 2 3 4 5 6 7 8"<<endl;
cout<<" -┬-┬-┬-┬-┬-┬-┬-"<<endl;
output();
cout<<"重新输入请按 b ,退出请按 q"<<endl;
ef:cin>>put;
switch(put)//程序结束功能
{
case 'b': goto cd; break;
case 'q': goto gh; break;
default: cout<<"输入错误,请重新输入!"<<endl; goto ef;
}
gh:cout<<endl;
cout<<"********************************************************************************";
cout<<"*************************谢谢使用,马踏棋盘算法程序*****************************";
cout<<"********************************************************************************";
}
using namespace std;
struct stack
{
int x;
int y;
int NextStep;//下一步
int CallOrder[8];//访问顺序
struct stack *back;
};
const int N=8;
int board[N][N];
int try1[]={-2,-1,1,2,2,1,-1,-2};
int try2[]={1,2,2,1,-1,-2,-2,-1};
int GetValue(const int x,const int y) //取x,y的权值
{
int count=0,i,x1,y1;
for(i=0;i<N;i++)
{
x1=x+try1[i];
y1=y+try2[i];
if(x1>=0&&x1<N&&y1>=0&&y1<N&&!board[x1][y1])
count++;//如果点落在棋盘内,则权值加1
}
return count;
}
/*进栈*/
stack *push(const int x,const int y,stack *top,const int NextStep)
{
stack *p=new stack;
int x1,y1,i,j,k=0;
int values[N];
//取得各点权值
for(i=0;i<N;i++)
{
x1=x+try1[i];
y1=y+try2[i];
if(x1<0||x1>N-1||y1<0||y1>N-1||board[x1][y1])
values[i]=-1;//该位置不能踏,权值减1
else
values[i]=GetValue(x1,y1);
}
//对values进行排序
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
if(values[j]==i)
p->CallOrder[k++]=j;
}
p->CallOrder[k]=-1;
p->x=x;
p->y=y;
p->NextStep=NextStep;
p->back=top;
return p;
}
//出栈
stack *pop(stack *top,stack& work)
{
work=*top;
top=top->back;
return top;
}
/*输入起始位置*/
void input(int& x,int& y)
{
while(1)
{
cout<<"请输入马的起始“行”坐标:(1~8)";
cin>>x;
cout<<"请输入马的起始“列”坐标:(1~8)";
cin>>y;
if(x>0&&x<=N&&y>0&&y<=8)
{
x-=1;
y-=1;
break;
}
}
}
void output()//输出
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
if(board[i][j]<10)
cout<<" "<<board[i][j]<<" ";
else
cout<<" "<<board[i][j];
cout<<endl;
}
}
void initialize()//初始化
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
board[i][j]=0;
}
/*主函数*/
void main()
{
cout<<"********************************************************************************";
cout<<"***************************欢迎使用马踏棋盘算法程序*****************************";
cout<<"********************************************************************************";
cout<<"******************************** 进入程序请按 a ********************************";
cout<<"********************************************************************************";
void output();
/*界面选择*/
char put;
ab:cin>>put;
if(put!='a')
{
cout<<"输入错误,请重新输入!";
goto ab;
}
cd:void input(int&,int&);
void initialize();
int count=1;
int i,x1,y1;
stack *top=NULL,work;
input(x1,y1);//输入起始位置
initialize();//初始化
board[x1][y1]=count++;
top=push(x1,y1,top,0);
while(1)
{
top=pop(top,work);
for(i=work.NextStep;i<N&&work.CallOrder[i]!=-1;)
{
x1=work.x+try1[work.CallOrder[i]];
y1=work.y+try2[work.CallOrder[i]];
top=push(work.x,work.y,top,i+1);
board[x1][y1]=count++;
work.x=x1;
work.y=y1;
i=0;
top=push(x1,y1,top,0);
top=pop(top,work);
}
if(count>N*N)
break;
board[x1][y1]=0;
count--;//回溯
}
cout<<endl;
cout<<"棋盘如下,走法按数字顺序"<<endl;
cout<<endl;
cout<<" 1 2 3 4 5 6 7 8"<<endl;
cout<<" -┬-┬-┬-┬-┬-┬-┬-"<<endl;
output();
cout<<"重新输入请按 b ,退出请按 q"<<endl;
ef:cin>>put;
switch(put)//程序结束功能
{
case 'b': goto cd; break;
case 'q': goto gh; break;
default: cout<<"输入错误,请重新输入!"<<endl; goto ef;
}
gh:cout<<endl;
cout<<"********************************************************************************";
cout<<"*************************谢谢使用,马踏棋盘算法程序*****************************";
cout<<"********************************************************************************";
}