#include <stdio.h>
#include <stdlib.h>
#define M 8 //行
#define N 8 //列
?
typedef struct snode?? ?//坐標(biāo)
{
?? ?int flag;
?? ?int x;
?? ?int y;
}stack;
typedef struct node?? ??? ?
{
?? ?int top;?? ?//記錄走了多少步top+1
?? ?int flag; ?//記錄上一步走的方向
?? ?stack * p;?? ?//路徑棧
}LNode;
?
LNode * CreateStacke();?? ??? ?//創(chuàng)建，并初始化
void Judge(LNode * s, int chess[][N]); //判斷往哪走
void Push(LNode * s, stack x); ?//入棧操作
void Pop(LNode * s); //出棧操作
int IsFull(LNode * s); //判滿
int IsEmpty(LNode * s); //判空?
int main()
{
?? ?int chess[M][N] = {0};?? ??? ?//棋盤
?? ?int i, j; ?//循環(huán)變量
?? ?LNode * step;?? ??? ??? ??? ??? ?//step存的是走的路徑
?? ?
?? ?step = CreateStacke();
?? ?
?? ?Judge(step, chess);
?
?? ?for (i = 0; i < N; i++){
?? ??? ?for (j = 0; j < M; j++){
?? ??? ??? ?printf("%2d ", chess[i][j]);
?? ??? ?}
?? ??? ?printf("\n");
?? ?}
?
?? ?return 0;
}
LNode * CreateStacke()
{
?? ?LNode * s = (LNode *)malloc(sizeof(LNode));
?? ?
?? ?if (!s){
?? ??? ?printf("內(nèi)存空間不足!\n");
?? ??? ?system("pause");
?? ??? ?exit(0);
?? ?}
?? ?s->p = (stack *)malloc(sizeof(stack) * M * N);
?? ?if (!s->p){
?? ??? ?printf("內(nèi)存空間不足!\n");
?? ??? ?system("pause");
?? ??? ?exit(0);
?? ?}
?? ?s->top = -1;?? ?// 把top放在棧底
?? ?return s;
}
void Judge(LNode * s, int chess[][N])?? ??? ?
{
?? ?int ch[8][2] = {?? ??? ??? ??? ??? ??? ?//馬可能走的八個方向
?? ??? ??? ??? ??? ?{1, -2}, { 2, -1},
?? ??? ??? ??? ??? ?{2, 1 }, { 1, 2 },
?? ??? ??? ??? ??? ?{-1, 2}, {-2, 1 },
?? ??? ??? ??? ??? ?{-2, -1},{-1, -2}
?? ??? ??? ??? ?};
?? ?int i, j = 1, flag = 1;
?? ?stack t;
?
?? ?printf("請輸入馬的初始位置：(%d * %d)\n", M, N);
?? ?scanf("%d%d", &t.y, &t.x);
?? ?if (t.x <= 0 || t.x > N || t.y <= 0 || t.y > N){
?? ??? ?printf("輸入的坐標(biāo)超出范圍！\n");
?? ??? ?exit(0);
?? ?}
?? ?t.x--;
?? ?t.y--;
?? ?chess[t.y][t.x] = 1;?? ??? ??? ??? ?//選擇馬的第一個落腳點
?? ?Push(s, t);
?? ?while (s->top < M * N - 1 && s->top != -1){
?? ??? ?for (i = 0; i < 8; i++){
?? ??? ??? ?t.x = s->p[s->top].x + ch[i][0];
?? ??? ??? ?t.y = s->p[s->top].y + ch[i][1];
?? ??? ??? ?//如果它的坐標(biāo)沒有超出范圍，并且沒有走過，則把該路線存入路徑棧
?? ??? ??? ?if (t.x >= 0 && t.y >= 0 && t.x < N && t.y < M && !chess[t.y][t.x]){?? ??? ?
?? ??? ??? ??? ?if(flag){?? ??? ??? ?//沒有退回去
?? ??? ??? ??? ??? ?Push(s, t);
?? ??? ??? ??? ??? ?chess[t.y][t.x] = s->top + 1;
?? ??? ??? ??? ??? ?s->p[s->top - 1].flag = i;
?? ??? ??? ??? ??? ?flag = 1;
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else{?? ??? ??? ??? ?//退回去了
?? ??? ??? ??? ??? ?if (s->p[s->top].flag < i){?? ??? ?//重新走時，讓它的方向不等于原先的方向
?? ??? ??? ??? ??? ??? ?flag = 1;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}?? ?
?? ??? ?//如果沒有能走的路時，即，所有的路徑都超出范圍，或者，該位置已經(jīng)走過了，則，退到上一步，重新選擇；
?? ??? ?if (i == 8){
?? ??? ?
?? ??? ??? ?chess[s->p[s->top].y][s->p[s->top].x] = 0;
?? ??? ??? ?Pop(s);
?? ??? ??? ?flag = 0;
?? ??? ?}
?? ?}
}
void Push(LNode * s, stack x)
{
?? ?if (IsFull(s)){
?? ??? ?printf("棧上溢，不能進(jìn)行入棧操作!\n");
?? ??? ?exit (0);?
?? ?}
?? ?else{
?? ??? ?s->top++;
?? ??? ?s->p[s->top] = x;
?? ??? ?
?? ?}
}
void Pop(LNode * s)
{
?? ?if (IsEmpty(s)){
?? ??? ?printf("棧為空，不能進(jìn)行出棧操作!\n");
?? ??? ?exit(0);
?? ?}
?? ?s->top--;
}
int IsFull(LNode * s)
{
?? ?if (s->top >= M * N){
?? ??? ?return 1;
?? ?}
?? ?else{
?? ??? ?return 0;
?? ?}
}
int IsEmpty(LNode * s)
{
?? ?if (s->top == -1){
?? ??? ?return 1;
?? ?}
?? ?else{
?? ??? ?return 0;
?? ?}
}