2017长沙艺考校考考点:跳马问题

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);

　　}