马遍历棋盘详细

/*
 马遍历棋盘的问题。通常有两种：
 1.从一点到另外一点的最短距离
 2.一次能否遍历整个M*N的棋盘
 方法：都是递归。根据需要一个修改全局数据，另外一个修改局部数据。
 2008.7.7 林汉杰
*/

/*
 这是从一个点跳到棋盘上的任意一点的最短的步数
 这个例子跟我写的c c++的迷宫解法 相当类似
 通过递归，修改全局变量寻找最优方案
 骑士聚会问题以这个问题为基础，不过也没有什么其他的了
*/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#define M 5
#define N 5
 
static int chessboard[M][N];
 
void jump(int i,int j, int prei,int  prej) {
        if(i < 0 || i >= M || j < 0 || j >= N)return;
        if(chessboard[prei][prej] + 1 > chessboard[i][j] && chessboard[i][j] > 0)return;
        chessboard[i][j] = chessboard[prei][prej] + 1;
        jump(i+1, j+2, i, j);
        jump(i+1, j-2, i, j);
        jump(i-1, j+2, i, j);
        jump(i-1, j-2, i, j);
        jump(i+2, j+1, i, j);
        jump(i+2, j-1, i, j);
        jump(i-2, j+1, i, j);
        jump(i-2, j-1, i, j);
}
 
int main() {
       
        int starti, startj;
        printf("enter i,j:");
        scanf("%d %d", &starti, &startj);
        if(starti < 0 || starti >= M || startj < 0 || startj >= N) {
                printf("enter error\n");
                getchar();
                return 0;
        }
        fflush(stdin);
        jump(starti ,startj ,starti ,startj);
        for(int i=0; i                for(int j=0; j                        printf("%d\t", chessboard[i][j]);
                }
                printf("\n");
        }
        printf("\n");
        getchar();
        return 0;
}

 

/*
 这是一次走遍棋盘的的程序。如果找到路径就立即跳出。
 用递归，通过改变栈中的数据寻找路径
*/

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "setjmp.h"
 
#define M 5
#define N 5

jmp_buf my_jmp;

struct step_t {
        int i;
        int j;
        int val;
};
 
struct step_t steps[M*N];
 
 
void jump(int i, int j, int step) {
        if(i < 0 || i >= M || j < 0 || j >= N)return;
        for(int k=0; k                if(i == steps[k].i && j == steps[k].j)return;
        }
        steps[step].i = i;
        steps[step].j = j;
        steps[step].val = step+1;
 
        if(step == M*N-1) {
                printf("done\n");
                longjmp(my_jmp, 1);
        }
 
        jump(i+1, j+2, step+1);
        jump(i+1, j-2, step+1);
        jump(i-1, j+2, step+1);
        jump(i-1, j-2, step+1);
        jump(i+2, j+1, step+1);
        jump(i+2, j-1, step+1);
        jump(i-2, j+1, step+1);
        jump(i-2, j-1, step+1);
}
 
int main() {
 
        int result = setjmp(my_jmp);
  if(result == 0) {
   jump(2, 2, 0);
  } else if(result == 1) {
                printf("\nresult...\n");
                for(int k=0; k                        printf("step[%d][%d]:%d\n", steps[k].i, steps[k].j, steps[k].val);
                }
        } else {
                printf("no result exit\n");
        }
        getchar();
        return 0;
}