Code:
#include <stdio.h>
#include <stdlib.h>
#define maxM 50
#define maxN 50
#define bool short
#define true 1
#define false 0
const short dirt[][] =
{{2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
/* global varibles */
short m, n, half_tree;
short jw[maxM][maxN]; // jw = jump way
bool exist_way;
/* End of global varibles */
void extra_find(short x, short y, short *depth)
{
int new_x, new_y, i;
for (i = 0; i < 8; i++) {
new_x = x+dirt[i][0];
new_y = y+dirt[i][1];
if ((new_x >= 0) && (new_y < m) && (new_y >= 0) && (new_y < n))
if (jw[new_x][new_y] == 0) {
jw[new_x][new_y] = half_tree + *depth;
if (*depth == m*n) {
exist_way = true;
exit(0);
}
else extra_find(new_x, new_y, &((*depth)++));
jw[new_x][new_y] = 0;
}
}
}
void find(short x, short y, short *depth)
{
short x_coord, y_coord, new_x, new_y, max_depth, i;
bool expand;
x_coord = x;
y_coord = y;
expand = false;
for (i = 0; i < 8; i++) {
new_x = x+dirt[i][0];
new_y = y+dirt[i][1];
if ((new_x >= 0) && (new_y < m) && (new_y >= 0) && (new_y < n))
if (jw[new_x][new_y] == 0) {
expand = true;
jw[new_x][new_y] = *depth;
if (*depth == m*n) exit(0);
else if (*depth < half_tree)
find(new_x, new_y, &((*depth)++));
jw[new_x][new_y] = 0;
}
}
if (!expand) {
max_depth = *depth;
extra_find(x_coord, y_coord, &max_depth);
}
}
void double_bfs()
{
short x_coord, y_coord, i, j;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
jw[i][j] = 0;
for (x_coord = 0; x_coord < m; x_coord++)
for (y_coord = 0; y_coord < n; y_coord++) {
jw[x_coord][y_coord] = 1;
find(x_coord, y_coord, 2);
}
}
int main()
{
FILE *fr, *fw;
short i, j;
fr = fopen("horse.dat", "rt");
fw = fopen("horse.out", "wt");
fscanf(fr, "%d %d", &m, &n);
half_tree = (int)((m*n)/2);
double_bfs();
if (exist_way)
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++)
fprintf(fw, "%4d", jw[i][j]);
fprintf(fw, "\n");
}
else fprintf(fw, "No solution.");
fclose(fr);
fclose(fw);
return 0;
}