中国象棋马走日(要求打印每一种走法) — 递归

以你之姓@ 2022-03-07 01:16 340阅读 0赞

[https://www.cnblogs.com/houjun/p/6507691.html][https_www.cnblogs.com_houjun_p_6507691.html]

//在半个中国象棋棋盘上,马在左下角(1，1)处,马走日字,  
//而且只能往右走...不能向左...可上可下...求从起点到(m, n)处有  
//几种不同的走法（函数的递归调用）  
//要求打印出每一种走法

\#include<stdio.h>  
\#include<stdlib.h>

int counter = 0;  
//一个点的结构  
typedef struct Point  
\{  
    int x;  
    int y;  
\}Point;

//定义一个结构体保存路径  
typedef struct Step  
\{  
    int num;  
    Point steps\[9\];  
\}Step;  
//声明一个路径结构体全局变量，并初始化  
Step trace = \{-1,\{1,1\}\};

//声明函数  
void print();  
int horse(int x1,int y1,int x2,int y2);

int main()  
\{  
    char ch;  
    while(ch != EOF)  
    \{  
        int m,n;  
        counter = 0;  
        printf("请输入目的地址,用英文逗号隔开，如2,3：\\n");  
        if(scanf("%d,%d",&m,&n) < 2)  
            printf("输入有不全，请重新输入！\\n");  
        else if(m>9||m<1||n>5||n<1)  
                printf("输入有误，请重新输入！\\n");  
            else  
                printf("共有%d种走法\\n",horse(1,1,m,n));  
        printf("\\n输入ctrl+z退出,任意键继续\\n");  
        getchar();  
        ch = getchar();  
        system("cls");  
    \}  
    return 0;  
\}

int horse(int x1,int y1,int x2,int y2)  
\{  
    int result = 0;  
    //创建并添加该点  
    Point po = \{x1,y1\};  
    trace.steps\[++trace.num\] = po;  
    if(x2 < x1  || (x1==x2 && y1 != y2))  
    \{  
        trace.num--;    //返回前，去除该点  
        return 0;  
    \}  
      
    if(x1 == x2 && y1 == y2)  
    \{  
        counter++;  
        print();  
        trace.num--;    //返回前，去除该点  
        return 1;  
    \}  
      
    if(x1+1 <= 9 && y1+2 <= 5)  
        result+=horse(x1+1,y1+2,x2,y2);  
    if(x1+1 <= 9 && y1-2 >0)  
        result+=horse(x1+1,y1-2,x2,y2);  
    if(x1+2 <= 9 && y1+1 <= 5)  
        result+=horse(x1+2,y1+1,x2,y2);  
    if(x1+2 <= 9 && y1-1 > 0)  
        result+=horse(x1+2,y1-1,x2,y2);

trace.num--;        //返回前，去除该点  
    return result;  
\}

void print()  
\{  
    int i;  
    printf("第%d种走法为：",counter);  
    for(i = 0;i <= trace.num;i++)  
    \{  
        printf("\[%d,%d\] ",trace.steps\[i\].x,trace.steps\[i\].y);  
    \}  
    printf("\\n");  
\}

[https_www.cnblogs.com_houjun_p_6507691.html]: https://www.cnblogs.com/houjun/p/6507691.html