苹果自己制作铃声软件:跳马问题
按日字跳马,
要求不重复地跳经所有方格。
求出所有跳马方案?
int map[12][12], status[12][12],kp;
int c[8][2]={{2,1},{2,-1},{1,2},{1,-2},
{-2,1},{-2,-1},{-1,2},{-1,-2}};
void prt(int a[][12]) /* 打印棋盘状态 */
{int i,j,i2,j2;
printf("\n");
for (i=2;i<=9;i++)
{ for (j=2;j<=9;j++) printf("%4d",a[i][j]);
printf("\n");
}
}
void status2(void) /* 计算棋盘各点条件数 */
{ int i,j,k,i2,j2,kz;
for(i=0;i<12;i++)
for(j=0;j<12;j++)
status[i][j]=100;
for(i=2;i<=9;i++)
for(j=2;j<=9;j++)
{kz=0;
for (k=0;k<=7;k++)
{i2=i+c[k][0];j2=j+c[k][1];
if (map[i2][j2]<50) kz++;
}
status[i][j]=kz;
}
prt(status);
}
void sort1(int b1[],int b2[]) /* 对8个可能的方向按条件数排序 */
{int i,j,mini,t; /*b1[]记录状态值(升序),b2[]记录排序后的下标 */
for (i=0;i<7;i++) <br>
{mini=i;
for (j=i+1;j<=7;j++)
if (b1[j]<b1[mini]) mini=j;
t=b1[i];b1[i]=b1[mini];b1[mini]=t;
t=b2[i];b2[i]=b2[mini];b2[mini]=t;
}
}
void init1(void) /* 初始化 */
{int i,j,k;
for(i=0;i<12;i++)
for(j=0;j<12;j++)
map[i][j]=100;
for(i=2;i<=9;i++)
for(j=2;j<=9;j++)
map[i][j]=0;
status2();
}
void search(int i2,int j2) /* 利用递归回溯进行搜索 */
{int b1[8],b2[8],i,i3,j3;
kp++;
if(kp==65)
{prt(map); exit(0); }
for(i=0;i<=7;i++)
{b2[i]=i;
b1[i]=status[i2+c[i][0]][j2+c[i][1]];
}
sort1(b1,b2);
for(i=0;i<=7;i++)
{i3=i2+c[b2[i]][0]; j3=j2+c[b2[i]][1];
if (map[i3][j3]==0)
{ map[i3][j3]=kp; search(i3,j3); map[i3][j3]=0;
}
}
kp--;
}
main()
{init1(); >
map[5][2]=1; kp=1;
search(5,2);
}