马踏棋盘问题求解
#include<stdio.h>#include<malloc.h>
#include<stdlib.h>
#define M 8
//宏定义棋盘大小
//#define SIZE 100
int board[M][M];
typedef struct direct
{
int r,c,pathnum ; //在棋盘中的位置和可走方向的数目
}dir;
//用来计算当前位置可走的方向数目
int pathnum(int row,int cn)
{
int a,b,count=0 ;
a=row ;
b=cn ;
//当前位置可选方向可以走通，则数目加一
if(a-2>=0&&b-1>=0&&board[a-2][b-1]==0) 为什么board[a-2][b-1]==0，不是刚开始数组的值是不确定的吗？？？
count++;
if(a-2>=0&&b+1<M&&board[a-2][b+1]==0)
count++;
if(a+2<M&&b-1>=0&&board[a+2][b-1]==0)
count++;
if(a+2<M&&b+1<M&&board[a+2][b+1]==0)
count++;
if(a-1>=0&&b+2<M&&board[a-1][b+2]==0)
count++;
if(a-1>=0&&b-2>=0&&board[a-1][b-2]==0)
count++;
if(a+1<M&&b+2<M&&board[a+1][b+2]==0)
count++;
if(a+1<M&&b-2>=0&&board[a+1][b-2]==0)
count++;
return count ;
}
//寻找路径函数
void findway(int m,int n)
{
dir f[8],path ;
int i,j,k, stepnum ;
stepnum=1 ;
i=m ;
j=n ;
while(stepnum<M*M&&i<M&&j<M&&i>=0&&j>=0)
{
board[i][j]=stepnum ;
//用来标志可走方向数的最小值
path.pathnum=8 ;
//对方向数组赋初值
for(k=0;k<8;k++) 这里为什么赋值为-1？？？
{
f[k].r=-1 ;
f[k].c=-1 ;
}
//如果第一个方向可走，则将坐标及可选方向数赋给f[0]，以下同理
if(i-2>=0&&j-1>=0)
{
f[0].r=i-2 ;
f[0].c=j-1 ;
f[0].pathnum=pathnum(f[0].r,f[0].c);
}
if(i-2>=0&&j+1<M)
{
f[1].r=i-2 ;
f[1].c=j+1 ;
f[1].pathnum=pathnum(f[1].r,f[1].c);
}
if(i+2<M&&j-1>=0)
{
f[2].r=i+2 ;
f[2].c=j-1 ;
f[2].pathnum=pathnum(f[2].r,f[2].c);
}
if(i+2<M&&j+1<M)
{
f[3].r=i+2 ;
f[3].c=j+1 ;
f[3].pathnum=pathnum(f[3].r,f[3].c);
}
if(i-1>=0&&j+2<M)
{
f[4].r=i-1 ;
f[4].c=j+2 ;
f[4].pathnum=pathnum(f[4].r,f[4].c);
}
if(i-1>=0&&j-2>=0)
{
f[5].r=i-1 ;
f[5].c=j-2 ;
f[5].pathnum=pathnum(f[5].r,f[5].c);
}
if(i+1<M&&j-2>=0)
{
f[6].r=i+1 ;
f[6].c=j-2 ;
f[6].pathnum=pathnum(f[6].r,f[6].c);
}
if(i+1<M&&j+2<M)
{
f[7].r=i+1 ;
f[7].c=j+2 ;
f[7].pathnum=pathnum(f[7].r,f[7].c);
}
//寻找当前位置的八个方向中的可走方向数最少的方向作为新的方向
for(k=0;k<8;k++)
if(f[k].r>=0&&f[k].c>=0&&f[k].pathnum<=path.pathnum&&board[f[k].r][f[k].c]==0&&f[k].pathnum>0)
{
path.pathnum=f[k].pathnum;
path.r=f[k].r ;
path.c=f[k].c ;
}
i=path.r ;
j=path.c ;
stepnum++;
}
}
void main()
{
int r,c,i,j ;
printf("请输入马在棋盘上的首位置\n");
scanf("%d,%d",&r,&c);
findway(r,c);
printf("\n");
//输出棋盘上的路径
for(i=0;i<M;i++)
{
for(j=0;j<M;j++)
printf("%3d",board[i][j]);
printf("\n");
}
}
