跳马问题非递归.cpp

跳马问题

/*
*思路是，马按要求不断向前跳，跳到头或跳到不能跳的地方，则回跳。
*马能跳到的地方，标记为1。输出标记为1的点的坐标。
*/
#include<iostream>
#include<fstream> 
#include<string>
using  namespace std;

struct node{
  int row,line,choice;//row和line分别表示行数和列数，每个点跳有8个方向，choice表示选择的方向
  node *next, *prior;
};

int n=0;//用来计算是跳的第几步
int board[10][9];//棋盘

//输出
void outcome(int c)
{
	//逐行逐列打印马能跳到的坐标
	int i,j,count=0;
	for(i=0;i<10;i++)
		for(j=0;j<9;j++)
			if(board[i][j]!=0)
			{
				count++;
				cout<<"可能的第"<<count<<"个坐标是：("<<i+1<<","<<j+1<<")\n";
			}
}

//跳步
void jump(int c,int x,int y,node *&q)
{
	node *&p = new node;
	//选择跳步方向
	switch(c)
	{
	case 1: x=x-2;y=y+1;break;
	case 2: x=x-2;y=y-1;break;
	case 3: x=x-1;y=y-2;break;
	case 4: x=x+1;y=y-2;break;
	case 5: x=x+2;y=y-1;break;
	case 6: x=x+2;y=y+1;break;
	case 7: x=x+1;y=y+2;break;
	case 8: x=x-1;y=y+2;break;
	}
	//插入刚刚跳的那一步
	p->row=q->row;
	p->line=q->line;
	p->choice=q->choice;
		q->prior->next=p;
		p->prior=q->prior;
		p->next=q;
		q->prior=p;
	q->row=x;
	q->line=y;
	q->choice=1;//刚插入的那一步的方向初始化为0
	n++;//计数
}

//回跳
void jumpback(node *&q)
{
	//删除尾端的一步
	node *p;
	p=q->prior;
	q->row=p->row;
	q->line=p->line;
	q->choice=p->choice;
	
	p->prior->next=q;
	q->prior=p->prior;
	delete p;
	q->choice++;//方向变更
	n--;//回跳相当于又少跳了一步
}



void main()
{
	char filename[80];
	cout<<"请输入要打开的文件名：";
	cin>>filename;
	ifstream fin(filename);
	if(!fin) cout<<"文件打开失败！"<<endl;//当文件不存在时给出提示

	int x,y,k;//x，y表示起点位置，k表示需跳的步数
	node *&h = new node;
	node *&track = new node;//表示当前正在跳的路线的轨迹
	node *&t = new node;
	track->next=t;
	t->prior=track;
	track->prior=h;
	h->prior=NULL;
	track->choice=1;//初始化为第一个方向
	fin>>x>>y>>k;//读入数据文件

	track->row=x;
	track->line=y;

	while(n<k)
	{
		if(track->choice>8)
		{
			//如果方向变更超出8了，说明该点的8个方向已跳完，该回跳
			if(n>0) jumpback(track);
			else break;//若此8个方向已跳完的点是起步的点，则跳出循环
		}
		else
		{
			jump(track->choice,track->row,track->line,track);

			if(track->row<1 || track->row>10 || track->line<1 || track->line>9) 
				jumpback(track);//如果跳出棋盘外，则回跳
			else if(n==k)
			{
				board[track->row-1][track->line-1]=1;//到达了该跳的步数，标记此坐标
				jumpback(track);//回跳到上一步
			}
		}
	}
	outcome(board[10][9]);
	fin.close();
}