Question

一道C++题，急求！

武士巡逻问题
【基本要求】
在西洋棋中的武士与象棋的马相似，走的是L型的路，请用非递归的程序，输入一个表示棋盘大小值的n，在输入一个起点的坐标，找出一条从那一个起点，可以让武士棋走完n^2格而不重复的路径。
【测试数据】
在棋盘各个格子都定义成EMPTY。因为一共有n*n个格子，所以依着武士棋第一步、第二步、第三步、、、、第n*n步的顺序，在对应的格子中填入0，1，2，3，、、、n*n-1，因此在最后输出的时候，跟着这些数值就可以顺序走一次了。在走棋盘时会一再的尝试，并且做回溯的工作，因此用一个堆栈来保存到目前为止所经过的各个格的坐标，以及从这一格到下一格所使用的方向。这个堆栈实际上是三个数组，Path-x[] Path-[]存放格子的坐标，direction[]存放时用的方向 ，top指出堆栈最顶上元素何在，在开始时它的值是-1。
源代码我找到了，但是有BUG,而且是c的不是c++的，我不会改，求帮忙完成。。。。。。。。
链接附在下面：
http://www.neu.edu.cn/cxsj/ShowBlog.aspx?ID=218&BlogID=10

Answer 1

算了。我到抄袭了一个。就是你的链接那个。
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10 /* max. board size */
#define MAX_STACK 100 /* stack size = board-size^2*/
#define SUCCESS 1 /* return value for a succ. */
#define FAILURE 0 /* for a failure. */
#define EMPTY -1 /* value to indicate empty */

/* ----------------- external variables ----------------- */

int board[MAXSIZE+1][MAXSIZE+1]; /* chess board */
int n; /* working board size */
int offset_x[] = { 2, 1, -1, -2, -2, -1, 1, 2};
int offset_y[] = { 1, 2, 2, 1, -1, -2, -2, -1};

int path_x[MAX_STACK+1]; /* stack for x coordinate */
int path_y[MAX_STACK+1]; /* stack for y coordinate */
int direction[MAX_STACK+1]; /* stack for direction */
int top; /* stack pointer */

/* ----------------- function prototype ----------------- */

void initial(void);
void display(void);
int try_s(int, int);

/* -------------------- main program -------------------- */

void main(void)
{
int row, column;
char line[100];

printf("\nRecursive Knight Tour Problem");
printf("\n=============================");
printf("\n\nBoard Size ----> ");
gets(line);
n = atoi(line);
printf( "Start Row -----> ");
gets(line);
row = atoi(line);
printf( "Start Column --> ");
gets(line);
column = atoi(line);

initial();
if (try_s(row, column) == FAILURE)
printf("\nNO SOLUTION AT ALL.");
else
display();
}

/* ------------------------------------------------------ */
/* FUNCTION initial : */
/* initialize the chess board to EMPTY. */
/* ------------------------------------------------------ */

void initial(void)
{
int i, j;

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
board[i][j] = EMPTY;
}

/* ------------------------------------------------------ */
/* FUNCTION display : */
/* display to chess board. */
/* ------------------------------------------------------ */

#define DRAWGRID(N) { int i; \
printf("\n+"); \
for (i = 1; i <= N; i++) \
printf("--+"); \
}

#define DRAWLINE(N, r) { int i; \
printf("\n|"); \
for (i = 1; i <= N; i++) \
printf("%2d|",board[r][i]);\
}

void display(void)
{
int r;

printf("\n\nHere is One Possible Solution :\n");
DRAWGRID(n);
for (r = 1; r <= n; r++) {
DRAWLINE(n,r);
DRAWGRID(n);
}
}

/* ------------------------------------------------------ */
/* FUNCTION try : */
/* The main non-recursive backtrack working routine. */
/* ------------------------------------------------------ */

#define YES 1
#define NO 0
#define BOARD(x,y) (1<=x) && (x<=n) && (1<=y) && (y<=n)
#define CHECK(x,y) board[x][y] == EMPTY
#define PUSH(x,y) { top++; \
path_x[top] = x; path_y[top] = y; \
direction[top] = 0; \
board[x][y] = top; \
}

int try_s(int x, int y)
{
int new_x, new_y;
int found;

top = -1; /* initial to empty */
PUSH(x, y); /* push first pos. and dir. */
while (top < n*n-1) { /* loop until the board full*/
found = NO;
while (direction[top] < 8) { /* try all 8 pos. */
new_x = path_x[top] + offset_x[direction[top]];
new_y = path_y[top] + offset_y[direction[top]];
if (BOARD(new_x,new_y) && CHECK(new_x,new_y)) {
PUSH(new_x, new_y); /* a new pos. PUSH*/
found = YES; /* set flag */
break; /* try next pos. */
}
else
direction[top]++; /* OR try next dir*/
}
if (!found) /* if no new pos. is found */
if (top > 0) { /* do we have prev. item? */
board[path_x[top]][path_y[top]] = EMPTY;
direction[--top]++; /* YES, backtrack */
}
else
return FAILURE; /* otherwise, FAILURE */
}
return SUCCESS; /* all pos. visited. DONE */
}