# include<iostream>
//包含其它头文件
using namespace std;
const int StackInitSize = 10;
const int StackInc = 10;
typedef int SElemType;
struct SStack
{
SElemType* base, * top; //栈底指针,栈顶指针
int stacksize; //当前分配的存储容量
};
struct ChessStruct
{
int x, y; //起点位置
int X, Y; //棋盘尺寸
int** key;
};
bool StackInit(SStack& S) //栈的初始化
{
S.base = new SElemType[StackInitSize];
if (!S.base) return false;
S.top = S.base;
S.stacksize = StackInitSize;
return true;
}
bool Push(SStack& S, SElemType e) //入栈
{
SElemType* base;
if (S.top - S.base == S.stacksize)
{
base = (SElemType*)realloc(S.base, (S.stacksize + StackInc) * sizeof(SElemType));
if (!base) return false;
S.base = base;
S.top = S.base + S.stacksize;
S.stacksize += StackInc;
}
*S.top = e;
S.top++;
return true;
}
bool Pop(SStack& S, SElemType& e) //出栈
{
if (S.top == S.base) return false;
e = *--S.top;
return true;
}
bool isEmpty(SStack& S) //判断栈是否为空
{
if (S.top == S.base) return true;
else return false;
}
bool getTop(SStack S, SElemType& e) //获取栈顶元素
{
if (S.top == S.base)
return false;
SElemType* top = S.top - 1;
e = *top;
return true;
}
//题目要求的算法
//定义方向
int direction[2][8] = { {1,1,-1,-1,2,2,-2,-2},{2,-2,2,-2,1,-1,1,-1} };
bool judge(int x, int y, int X, int Y) //判断位置是否在棋盘内
{
if (x >= 0 && x < X && y >= 0 && y < Y)
return true;
else
return false;
}
//判断某位置是否有路可走
bool NextStep(int x, int y, ChessStruct& Chess, int& flag) //flag用于记录方向
{
int X_max, Y_max;
X_max = Chess.X;
Y_max = Chess.Y;
//定义方向
int direction[2][8] = { {1,1,-1,-1,2,2,-2,-2},{2,-2,2,-2,1,-1,1,-1} };
int i;
int tempx, tempy;
for (i = flag; i < 8; i++)
{
if (judge(x + direction[0][i], y + direction[1][i], X_max, Y_max) && Chess.key[x + direction[0][i]][y + direction[1][i]] == 0) //下一点在棋盘内并且该点没有被走过
{
x = x + direction[0][i];
y = y + direction[1][i];
flag = i;
return true;
}
}
return false;
}
void ChessInit(ChessStruct& Chess, int X, int Y, int x, int y) //棋盘初始化
{
Chess.X = X;
Chess.Y = Y;
Chess.x = x;
Chess.y = y;
Chess.key = new int* [X];
for (int i = 0; i < X; i++)
{
Chess.key[i] = new int[Y];
}
int i, j;
for (i = 0; i < X; i++)
{
for (j = 0; j < Y; j++)
{
Chess.key[i][j] = 0;
}
}
}
void PrintChess(ChessStruct &Chess) //棋盘打印
{
int i, j;
for (i = 0; i < Chess.X; i++)
{
for (j = 0; j < Chess.Y; j++)
{
cout << Chess.key[i][j] << "\t";
}
cout << endl;
}
}
bool houseRun(ChessStruct& Chess)
{
int X_max, Y_max, x, y;
X_max = Chess.X;
Y_max = Chess.Y;
x = Chess.x;
y = Chess.y;
//判断初始位置是否合法
if (x > X_max - 1 || y > Y_max - 1 || x < 0 || y < 0)
return false;
//初始化棋盘
int step = 1; //表示步数
Chess.key[x][y] = 1;
step++;
int flag = 0, temp; //临时变量
int way; //记录上一次的方向
SStack SS;
StackInit(SS);
Push(SS, flag);
while (step < X_max * Y_max + 1)
{
Pop(SS, flag);
if (NextStep(x, y, Chess, flag)) //传入的x, y是当前位置
{
x = x + direction[0][flag];
y = y + direction[1][flag];
Chess.key[x][y] = step;
Push(SS, flag + 1); //存入栈中的是“方向+1”
Push(SS, 0);
step++;
}
else
{
Chess.key[x][y] = 0;
getTop(SS, temp);
temp--; //取出时要方向-1
step--;
x = x - direction[0][temp];
y = y - direction[1][temp];
}
}
return true;
}
int main()
{
//定义马初始位置
int x, y;
x = 0;
y = 0;
//定义棋盘尺寸
int X_max, Y_max;
X_max = 5;
Y_max = 5;
//创建二维棋盘
struct ChessStruct Chess;
//棋盘初始化
ChessInit(Chess, X_max, Y_max, x, y);
//开始运行
if (houseRun(Chess))
PrintChess(Chess);
else
cout << "没有路径" << endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)