中国象棋中马的走法(回朔法)算法分析与设计

实验五：中国象棋中马的走法。（回溯法）1.问题描述：在4×5的棋盘上已知马的起始坐标(x,y)，求马能够返回到起始位置的不重复的所有不同走法的总数。问题分析：(1)读入马的起始位置，进行合法性判断；(2)从起始位置开始搜索，搜索方法采用深搜，累计总数；(3)输出结果。#includestdio.h#includestdlib.hintarray[2][8]={{-1,-1,-2,-2,2,2,1,1},{-2,2,1,-1,1,-1,2,-2}};//表示马跳的8个方向intchess[4][5];//表示棋盘，1：表示已经在较早的时候走过，0：则没有inttotal=0;//统计走法的个数intsx,sy;//(sx,sy)表示马的起始坐标voidfind_way(intp1,intp2);//回溯的过程voidmain(){inti,j;for(i=0;i4;i++)for(j=0;j5;j++)chess[i][j]=0;printf(输入马的起始坐标:\n);scanf(%d,&sx);scanf(%d,&sy);printf(sx=%d,sy=%d\n,sx,sy);if((sx0)||(sx=4)||(sy0)||(sy=5))printf(ERROR\n);else{chess[sx][sy]=1;find_way(sx,sy);//从起始位置开始试探printf(total=%d\n,total);getchar();}}voidfind_way(intp1,intp2){inti,pi,pj;for(i=0;i8;i++){//向8个方向试探pi=p1+array[0][i];pj=p2+array[1][i];if((sx==pi)&&(sy==pj))total++;//找到一种走法,(sx,sy)表示起点elseif((pi=0)&&(pi4)&&(pj=0)&&(pj5)&&(chess[pi][pj]==0)){//继续试探chess[pi][pj]=1;find_way(pi,pj);chess[pi][pj]=0;}}//for}测试报告1.输入马的起始（3.4）2.运行结果