|
|
发表于 2024-1-13 15:50:23
|
显示全部楼层
还有这个
/*
马步遍历和骑士巡游问题。
马步遍历：在N*N棋盘上某一点开始以马步遍历整个棋盘，但不要求最后回到起点。
骑士巡游：在马步遍历的基础上要求最后回到起点。
*/
#include <stdio.h>
#include <time.h>
//#define _PRINT_FULL_RESULT_
#define _PRINT_SOME_RESULT_
#define MAX_SIZE 20
#define MAX_STEP MAX_SIZE * MAX_SIZE
typedef struct
{
long x;
long y;
} STEP;
static long TryX[]={ -2, -1, 1, 2, 2, 1, -1, -2 };
static long TryY[]={ 1, 2, 2, 1, -1, -2, -2, -1 };
static char Board[MAX_SIZE + 4][MAX_SIZE + 4]; //棋盘，比实际棋盘大4，因为有2格是边界。
//边界为值为-1，空白值为0，有棋子为1。
static char ResultBoard[MAX_SIZE][MAX_SIZE]; //用于输出结果的棋盘。
static STEP Step[MAX_STEP]; //存储每一步的坐标。
static long CurStep; //当前步，第一步是0。
static long Results; //解的个数。
static long Hamilton; //能够回到起点的解的个数。
static long SIZES, STEPS; //实际的棋盘大小和步数。
FILE *fp; //用于记录结果的文件。
/* */
void Init(void) //棋盘初始化。
{
for(long i=0; i < SIZES + 4; i++)
{
for(long j=0; j < SIZES + 4; j++)
{
Board[j]=0;
}
}
for(long i=0; i < SIZES + 4; i++)
{
Board[0]= -1;
Board[SIZES + 3]= -1;
Board[0]= -1;
Board[SIZES + 3]= -1;
Board[1]= -1;
Board[SIZES + 2]= -1;
Board[1]= -1;
Board[SIZES + 2]= -1;
}
Results=0;
Hamilton=0;
}
/* */
void Disp(void) //打印棋盘状态
{
printf("\n-----------------------------------------\n");
for(long i=0; i < SIZES + 4; i++)
{
for(long j=0; j < SIZES + 4; j++)
{
printf("%2d ", Board[j]);
}
printf("\n");
}
}
/* */
void Result(void) //输出结果
{
long dx, dy;
dx=Step[CurStep].x - Step[0].x; //判断最后是否回到起点。
dy=Step[CurStep].y - Step[0].y;
Results++;
#ifdef _PRINT_FULL_RESULT_
printf("\n-------------- %ld --------------\n", Results);
fprintf(fp, "\n-------------- %ld --------------\n", Results);
#endif
if(dx * dx + dy * dy == 5)
{
Hamilton++;
#ifdef _PRINT_FULL_RESULT_
printf("---------- Hamilton %d ----------\n", Hamilton);
fprintf(fp, "---------- Hamilton %d ----------\n", Hamilton);
#endif
}
#ifdef _PRINT_FULL_RESULT_
for(long i=0; i < STEPS; i++)
{
ResultBoard[Step.x - 2][Step.y - 2]=i + 1;
}
for(long i=0; i < SIZES; i++)
{
for(long j=0; j < SIZES; j++)
{
printf("%4d", ResultBoard[j]);
fprintf(fp, "%4d", ResultBoard[j]);
}
printf("\n");
fprintf(fp, "\n");
}
#elif defined _PRINT_SOME_RESULT_
printf("\rResults: %ld, Hamiltons: %ld", Results, Hamilton);
#endif
}
/*
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 0 0 N 0 N 0 0 0 -1 -1
-1 -1 0 N 0 0 0 N 0 0 -1 -1
-1 -1 0 0 0 X 0 0 0 0 -1 -1
-1 -1 0 N 0 0 0 N 0 0 -1 -1
-1 -1 0 0 N 0 N 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 0 0 0 0 0 0 0 0 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
*/
void PutIt(void)
{
long NextX, NextY;
for(long i=0; i < 8; i++) //8个方向上尝试，
{
NextX=Step[CurStep].x + TryX;
NextY=Step[CurStep].y + TryY;
if(Board[NextX][NextY] == 0) //如果这个位置是空，
{
Board[NextX][NextY]=1; //放置一个马，
++CurStep;
Step[CurStep].x=NextX;
Step[CurStep].y=NextY; //计入步数，
if(CurStep == STEPS - 1) //如果步数达到最大步数（棋盘全满），
{
Result(); //输出结果。
}
PutIt(); //再做下一次尝试。
}
}
Board[Step[CurStep].x][Step[CurStep].y]=0; //如果8个方向都不为空，将这次的马拿走，
--CurStep; //并且步数倒退1步。
}
/* */
int main(void)
{
long SX, SY;
time_t begin_tm, end_tm;
#ifdef _PRINT_FULL_RESULT_
fp=fopen("horse.txt", "w");
#endif
printf("Board size ?(SIZE=?):");
scanf("%ld", &SIZES);
STEPS=SIZES * SIZES;
printf("Start at ?(X=?):");
scanf("%ld", &SX);
printf("Start at ?(Y=?):");
scanf("%ld", &SY);
begin_tm=time(&begin_tm);
Init();
CurStep=0;
Step[CurStep].x=SX + 1; //第一步由输入产生。
Step[CurStep].y=SY + 1;
Board[Step[CurStep].x][Step[CurStep].y]=1; //棋盘相应位置放置一个马。
#ifdef _PRINT_FULL_RESULT_
fprintf(fp, " - Board size: %d*%d, start at (%d,%d)\n", SIZES, SIZES, SX, SY);
#endif
PutIt(); //开始遍历。
end_tm=time(&end_tm);
#ifdef _PRINT_FULL_RESULT_
fprintf(fp, "\n-------------- END --------------\n");
fprintf(fp, "Results: %ld, Hamiltons: %ld\n", Results, Hamilton);
fprintf(fp, "-------------- %ld secs---------------\n", end_tm - begin_tm);
#endif
printf("\n-------------- END --------------\n");
printf("Results: %ld, Hamiltons: %ld\n", Results, Hamilton);
printf("-------------- %ld secs---------------\n", end_tm - begin_tm);
fclose(fp);
return 0;
} |
|
